Maths Olympiad Prep

Library / /50 of 56

Number theory Difficulty 7.0 National Olympiad Prove it JBMO

Problem:
Find all quadruples of positive integers (p,q,a,b)(p, q, a, b), where pp and qq are prime numbers and a>1a>1, such that
pa=1+5qb p^{a}=1+5 q^{b}

Solutions — 2

Solution 1

Solution:
First of all, observe that if p,qp, q are both odd, then the left hand side of the given equation is odd and the right hand side is even so there are no solutions in this case. In other words, one of these numbers has to be equal to 22 so we can discuss the following two cases:

- p=2p=2

In this case the given equation becomes
2a=1+5qb 2^{a}=1+5 q^{b}
Note that qq has to be odd. In addition, 2a1(mod5)2^{a} \equiv 1 \pmod{5}. It can be easily shown that the last equation holds if and only if a=4ca=4c, for some positive integer cc. Now, our equation becomes 24c1=5qb2^{4c}-1=5q^{b}, which can be written into its equivalent form
(4c1)(4c+1)=5qb (4^{c}-1)(4^{c}+1)=5q^{b}
Since qq is odd, it can not divide both 4c14^{c}-1 and 4c+14^{c}+1. Namely, if it divides both of these numbers then it also divides their difference, which is equal to 22, and this is clearly impossible. Therefore, we have that either qb4c1q^{b} \mid 4^{c}-1 or qb4c+1q^{b} \mid 4^{c}+1, which implies that one of the numbers 4c14^{c}-1 and 4c+14^{c}+1 divides 55. Since for c2c \geq 2 both of these numbers are greater than 55, we only need to discuss the case c=1c=1. But in this case 5qb=155q^{b}=15, which is obviously satisfied only for b=1b=1 and q=3q=3. In summary, (p,q,a,b)=(2,3,4,1)(p, q, a, b)=(2,3,4,1) is the only solution in this case.

- q=2q=2

In this case obviously pp must be an odd number and the given equation becomes
pa=1+52b p^{a}=1+5 \cdot 2^{b}
First, assume that bb is even. Then 2b1(mod3)2^{b} \equiv 1 \pmod{3}, which implies that 1+52b1+5 \cdot 2^{b} is divisible by 33, hence 3pa3 \mid p^{a} so pp must be equal to 33 and our equation becomes
3a=1+52b 3^{a}=1+5 \cdot 2^{b}
From here it follows that 3a1(mod5)3^{a} \equiv 1 \pmod{5}, which implies that a=4ca=4c, for some positive integer cc. Then the equation 3a=1+52b3^{a}=1+5 \cdot 2^{b} can be written into its equivalent form
32c1232c+12=52b2 \frac{3^{2c}-1}{2} \cdot \frac{3^{2c}+1}{2}=5 \cdot 2^{b-2}
Observe now that 32c1(mod4)3^{2c} \equiv 1 \pmod{4} from where it follows that 32c+121(mod2)\frac{3^{2c}+1}{2} \equiv 1 \pmod{2}. From here we can conclude that the number 32c+12\frac{3^{2c}+1}{2} is relatively prime to 2b22^{b-2}, so it has to divide 55. Clearly, this is possible only for c=1c=1 since for c>1c>1 we have 32c+12>5\frac{3^{2c}+1}{2}>5. For c=1c=1, we easily find b=4b=4, which yields the solution (p,q,a,b)=(3,2,4,4)(p, q, a, b)=(3,2,4,4).

Next, we discuss the case when bb is odd. In this case,
pa=1+52b1+522(mod3) p^{a}=1+5 \cdot 2^{b} \equiv 1+5 \cdot 2 \equiv 2 \pmod{3}
The last equation implies that aa must be odd. Namely, if aa is even then we can not have pa2(mod3)p^{a} \equiv 2 \pmod{3} regardless of the value of pp. Combined with the condition a>1a>1, we conclude that a3a \geq 3. The equation pa=1+52bp^{a}=1+5 \cdot 2^{b} can be written as
52b=pa1=(p1)(pa1+pa2++1) 5 \cdot 2^{b}=p^{a}-1=(p-1)(p^{a-1}+p^{a-2}+\cdots+1)
Observe that
pa1+pa2++11+1++1=a1(mod2) p^{a-1}+p^{a-2}+\cdots+1 \equiv 1+1+\cdots+1=a \equiv 1 \pmod{2}
so this number is relatively prime to 2b2^{b}, which means that it has to divide 55. But this is impossible, since a3a \geq 3 and p3p \geq 3 imply that
pa1+pa2++1p2+p+132+3+1=13>5 p^{a-1}+p^{a-2}+\cdots+1 \geq p^{2}+p+1 \geq 3^{2}+3+1=13>5
In other words, there are no solutions when q=2q=2 and bb is an odd number.

In summary, (a,b,p,q)=(4,4,3,2)(a, b, p, q)=(4,4,3,2) and (a,b,p,q)=(4,1,2,3)(a, b, p, q)=(4,1,2,3) are the only solutions.

Solution 2

Solution:
Analogously as in the first solution we conclude that at least one of the numbers pp and qq has to be even. Since these numbers are prime, this implies that at least one of pp and qq must be equal to 22. Therefore it is sufficient to discuss the following two cases:

- p=2p=2

In this case the given equation then becomes
2a=1+5qb 2^{a}=1+5q^{b}
From here, it follows that qq is an odd number. In addition, 2a1(mod5)2^{a} \equiv 1 \pmod{5}, which implies that a=4ca=4c, for some positive integer cc. Then the above equation can be written in its equivalent form
(2c1)(2c+1)(22c+1)=5qb (2^{c}-1)(2^{c}+1)(2^{2c}+1)=5q^{b}
Since 2c1,2c2^{c}-1, 2^{c} and 2c+12^{c}+1 are three consecutive integers, one of them must be divisible by 33. Clearly it is not 2c2^{c} implying that one of the numbers 2c12^{c}-1 and 2c+12^{c}+1 is divisible by 33. This implies that 3(2c1)(2c+1)(22c+1)3 \mid (2^{c}-1)(2^{c}+1)(2^{2c}+1) so 35qb3 \mid 5q^{b}, hence qq must be equal to 33 and we are left with solving the equation
(2c1)(2c+1)(22c+1)=53b (2^{c}-1)(2^{c}+1)(2^{2c}+1)=5 \cdot 3^{b}
Note that 22c+12(mod3)2^{2c}+1 \equiv 2 \pmod{3} so from the above equation it follows that 22c+12^{2c}+1 must be equal to 55, which implies that c=1c=1. For c=1c=1 we have b=1b=1, so we get (a,b,p,q)=(4,1,2,3)(a, b, p, q)=(4,1,2,3) as the only solution in this case.

- q=2q=2

In this case the given equation becomes
pa=1+52b p^{a}=1+5 \cdot 2^{b}
so clearly pp must be an odd number.

If aa is odd then we have
52b=(p1)(pa1+pa2++p+1) 5 \cdot 2^{b}=(p-1)(p^{a-1}+p^{a-2}+\cdots+p+1)
The second bracket on the right hand side is sum of aa odd numbers so it is an odd number. Due to the condition a>1a>1 we must have a3a \geq 3. But then
pa1+pa2++p+1p2+p+132+3+1>5 p^{a-1}+p^{a-2}+\cdots+p+1 \geq p^{2}+p+1 \geq 3^{2}+3+1>5
so we do not have solutions in this case. Therefore it remains to discuss the case when aa is even.

Let a=2ca=2c for some positive integer cc. Then we have the following equation
(pc1)(pc+1)=52b (p^{c}-1)(p^{c}+1)=5 \cdot 2^{b}
Note that pc1p^{c}-1 and pc+1p^{c}+1 are two consecutive even numbers so one of them is divisible by 22 but not by 44. Looking into the right hand side of the above equation, we conclude that this number must be equal to either 22 or 52=105 \cdot 2=10. In other words, either pc1{2,10}p^{c}-1 \in \{2,10\} or pc+1{2,10}p^{c}+1 \in \{2,10\} yielding the following possible values for pcp^{c}: 1,3,9,111,3,9,11. Clearly pc=1p^{c}=1 is impossible, whereas pc=3p^{c}=3 implies that (pc1)(pc+1)(p^{c}-1)(p^{c}+1) is not divisible by 55 so there are no solutions if pc=3p^{c}=3. Similarly, for pc=11p^{c}=11 we have that (pc1)(pc+1)(p^{c}-1)(p^{c}+1) is divisible by 33 so it can not be equal to 52b5 \cdot 2^{b} for any positive integer bb. Finally, if pc=9p^{c}=9, we have solution (a,b,p,q)=(4,4,3,2)(a, b, p, q)=(4,4,3,2).

In summary, (a,b,p,q)=(4,4,3,2)(a, b, p, q)=(4,4,3,2) and (a,b,p,q)=(4,1,2,3)(a, b, p, q)=(4,1,2,3) are the only solutions.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.