New Zealand Mathematical Olympiad Committee

2010 Squad Assignment One — Solutions

Number Theory

Due: Wednesday, 17th February 2010

1. Determine all primes p such that 5p + 4p4 is a square number.
Solution: If 5p + 4p4 = n2 then

5p = n2 − 4p4 = (n − 2p2 )(n + 2p2 ).

Since 5 is prime we must have n − 2p2 = 5a , n + 2p2 = 5b for integers 0 ≤ a < b such that
a + b = p.
If a = 0 then n = 2p2 + 1, and 5p = n + 2p2 = 4p2 + 1 ≡ 1 mod p. This shows that 5
and p are coprime, so by Fermat’s Little Theorem we also have 5p = 5 · 5p−1 ≡ 5 mod p.
It follows that 4 ≡ 0 mod p, so p must be 2. But 52 + 4(24 ) = 89 is not square, so a = 0
does not give a solution.
If a > 0 then 5 divides gcd(n − 2p2 , n + 2p2 ) = gcd(n − 2p2 , 4p2 ), so 5 must divide 4p2 .
Since p is prime this implies p = 5. Since 55 + 4 · 54 = 54 (5 + 4) = 32 (52 )2 this does indeed
give a solution. So the only solution is p = 5.

2. For each positive integer a we consider the sequence han i with a0 = a and an = an−1 +40n! .
Prove that every such sequence contains infinitely many numbers that are divisible by 2009.
Solution: Since 40 and 2009 are coprime we have 40k·φ(2009) ≡ 1 mod 2009, where φ is
the Euler totient function (also known as the Euler phi function). For n > φ(2009) the
exponent n! is a multiple of φ(2009), and we therefore have an+1 ≡ an + 1 mod 2009. This
means that for n > φ(2009) all values modulo 2009 are taken cyclicly and periodically,
and all values are obtained infinitely often. In particular, this holds for the value 0.

3. Find all integers k such that for every integer n, the numbers 4n + 1 and kn + 1 are
relatively prime.
Solution: Since 4n+1 is odd, the identity k −4 = k(4n+1)−4(kn+1) shows that 4n+1
and kn + 1 are relatively prime if k − 4 has no odd divisor p > 1, that is, if k − 4 = ±2m
for some nonnegative integer m.
On the other hand, if k − 4 has an odd divisor p > 1, then we can easily find a multiple
of p of the form 4n + 1 (for example, the number p2 , or simply one of the numbers p, 3p).
For any number 4n + 1 divisible by p, the above identity implies that p | kn + 1, hence
4n + 1 and kn + 1 are not relatively prime.
So the answer is k = 4 ± 2m , where m = 0, 1, 2, . . ..

1
4. Let n be a positive integer. Prove that if the sum of all of the positive divisors of n is a
perfect power of 2, then the number of those divisors is also a perfect power of 2.
Solution: If n = pr11 pr22 · · · prkk , where p1 , . . . , pk are distinct primes and ri ≥ 1 for each
i, then n has
Yk
(ri + 1)
i=1

divisors and their sum is

k
Y
(1 + pi + p2i + · · · + pri i )
i=1

(check that when this product is expanded every number of the form ps11 ps22 · · · pskk with
si ≤ ri occurs exactly once). If this is a power of two then each of the factors

fi = 1 + pi + p2i + · · · + pri i

must also be a power of two. Since fi > 1, both pi and ri must be odd. We will show
that ri = 1 for all i, so that the number of divisors is simply 2k .
Suppose that ri > 1. Then we may factor fi as

fi = (1 + pi )(1 + p2i + p4i + · · · + pri i −1 );

and since fi has no odd divisor greater than one the even integer ri − 1 (which is assumed
to be positive) must be of the form 4k + 2. This implies that we can factor further to get

fi = (1 + pi )(1 + p2i )(1 + p4i + p8i + · · · + pri i −3 ).

It follows that both 1 + pi and 1 + p2i are both powers of two. However, this is implies
1 + pi divides 1 + p2i , which is impossible: 1 + p2i = (1 + pi )(pi − 1) + 2, and 1 + pi - 2.
This completes the proof.
Alternate solution: The factorisation procedure above can be continued to get
t
fi = (1 + pi )(1 + p2i )(1 + p4i ) · · · (1 + p2i i ),

giving ri = 2ti +1 − 1. This gives a way to complete the problem without arguing that
1 + pi and 1 + p2i cannot both be powers of two.

5. (a) Show that there are infinitely many pairs of positive integers (m, n) such that
m+1 n+1
k= + (1)
n m
is a positive integer.
(b) Find all positive integers k such that (1) has a positive integer solution (m, n).
Solution: Suppose that m0 , n0 and k are positive integers such that
m0 + 1 n0 + 1
k= + ,
n0 m0

2
and consider the equation
m + 1 n0 + 1
k= + ,
n0 m
obtained by fixing n0 and allowing m to vary. This is equivalent to

m2 + (1 − kn0 )m + n20 + n0 = 0,

a quadratic in m with at least one root m = m0 . As such it will typically have a second
root m = m00 , and if this is a positive integer we will get a second solution to (1). With
any luck we’ll then be able to apply this again to get a third, and so on; so, let’s find
the second root and see if we can use this technique to generate an infinite sequence of
solutions, given one as a starting point.
To find the second root, observe that if x2 + ax + b = 0 has roots α1 , α2 , then

a = −(α1 + α2 ), b = α1 α2

(simply expand (x − α1 )(x − α2 ) and match co-efficients). So, if we know α1 is root, we

obtain the second as α2 = −a − α1 = b/α1 . In our case this gives m00 = kn0 − m0 − 1 =
(n20 + n0 )/m0 . The first expression for m00 shows that it’s an integer, and the second that
it’s positive; thus, if (m0 , n0 ) satisfies the conditions of the problem, so does

(m1 , n1 ) = (n0 , kn0 − m0 − 1) = (n0 , (n20 + n0 )/m0 ), (2)

with the same value of k.

Suppose now that m0 ≤ n0 . Then

n20 + n0 n0 (n0 + 1)
n1 = ≥ = n0 + 1 > m1 ,
m0 n0
so our new solution satisfies m0 ≤ n0 = m1 < n1 . Our new solution is therefore “larger”
than our original one (in the sense that m0 + n0 < m1 + n1 ), so if the equation has at least
one solution for a given value of k, it has infinitely many. To prove part (a) it therefore
suffices to find a single small solution; and since m = n = 1 clearly works (with k = 4)
we are done. Applying the transformation (2) to this solution we get the sequence (1, 1),
(1, 2), (2, 6), (6, 21), . . .
To prove part (a) we used (2) to show that, given one solution to the problem, we could
always find a larger one. To prove part (b) we will use the transformation to create
smaller solutions instead. Suppose this time that m0 > n0 . Then

n20 + n0 n0 (n0 + 1)
n1 = < = n0 + 1,
m0 n0
which gives n1 ≤ n0 = m1 . So our new solution satisfies m0 > n0 = m1 ≥ n1 , and is
“smaller” in the sense that m1 + n1 < m0 + n0 . This gives a descending sequence of
positive integer solutions (mi , ni ), all with the same value of k, that must terminate after

3
 finitely many steps. Since it can only terminate if mi = ni for some i, if there is a solution
for a given value of k, there must be one such that m = n. In this case we have
m+1 2
k=2 =2+ ,
m m
so m(k − 2) = 2. Therefore k = 3 (with solutions (2, 2), (2, 3), (3, 6), (6, 14), . . . ), or
k = 4, as found above.
Remark: The technique used here is known as root-flipping or Vieta jumping.

7p−1 − 1
6. (a) Find all primes p for which is a perfect square.
p
11p−1 − 1
(b) Find all primes p for which is a perfect square.
p
Solution: It is easy to check that p = 2 is not a solution to either equation, so we may
assume that p is odd. Suppose then that q p−1 − 1 = pn2 for q odd and p an odd prime.
Then
q p−1 − 1 = (q (p−1)/2 − 1)(q (p−1)/2 + 1) = pn2 ,
and since gcd(q (p−1)/2 − 1, q (p−1)/2 + 1) = 2 we must have either

(i) q (p−1)/2 − 1 = 2pa2 , q (p−1)/2 + 1 = 2b2 , or

(ii) q (p−1)/2 − 1 = 2a2 , q (p−1)/2 + 1 = 2pb2

for some integers a and b.

(a) Let q = 7. In (ii) above we would have −1 ≡ 2a2 ≡ (3a)2 mod 7, which is impossible
because −1 is not a square mod 7. So we must be in case (i). Since 7 ≡ 1 mod 6 we
have 6 | (q (p−1)/2 − 1) = 2pa2 , so 3 | pa2 . When p = 3 we have (72 − 1)/3 = 42 , so 3
is a solution. When p 6= 3 we must have 3 | a2 , so 9 | (q (p−1)/2 − 1); and since the
order of 7 modulo 9 is 3, we must then have 3 | (p − 1)/2.
Let k = (p − 1)/6. Then 2a2 = (7k + 1)(72k − 7k + 1) implies that 72k − 7k + 1 is a
perfect square. But this is not possible, because (7k − 1)2 < 72k − 7k + 1 < (7k )2 .
We conclude that p = 3 is the only solution.
(b) Let q = 11. In (i) above we would have 1 ≡ 2b2 mod 11, which is impossible as 2
is not a square mod 11. So this time we are in case (ii). From 11(p−1)/2 + 1 = 2pb2
we have 11(p−1)/2 ≡ −1 mod p, so 2a2 = 11(p−1)/2 − 1 ≡ −2 mod p. Hence a2 ≡
−1 mod p, implying p ≡ 1 mod 4. We can therefore factor to get

2a2 = 11(p−1)/2 − 1 = (11(p−1)/4 − 1)(11(p−1)/4 + 1),

so either
i. 11(p−1)/4 + 1 = c2 , giving 11(p−1)/4 = (c − 1)(c + 1), which is impossible, since
c − 1 and c + 1 can’t both be powers of 11; or
ii. 11(p−1)/4 + 1 = 2d2 , which is impossible since 2 is not a square mod 11.

4
 We conclude that there is no prime p for which the given quotient is a square.

7. Prove that there exist infinitely many natural numbers n with the following properties:
n can be expressed as a sum of two squares, n = a2 + b2 , and as a sum of two cubes,
n = c3 + d3 , but can’t be expressed as a sum n = x6 + y 6 of two sixth powers, where
a, b, c, d, x, y are natural numbers.
Solution: We show that numbers of the form n = 8(s6 + t6 ) satisfy the requirements.
Clearly, such a number is a sum of cubes; to see that it can be represented as a sum of
squares observe that

n = 2(2s3 )2 + 2(2t3 )2 = (2s3 − 2t3 )2 + (2s3 + 2t3 )2 .

We must now show that such a number cannot be expressed as a sum of sixth powers.
Suppose that there is a natural number solution (s, t, u, v) to 8(s6 + t6 ) = u6 + v 6 , and
consider one such that the sum s + t + u + v is minimal. Our aim is to find a second
solution (s0 , t0 , u0 , v 0 ) such that s0 + t0 + u0 + v 0 < s + t + u + v, and we will do this by
showing that u and v are even.
Clearly, u and v must have the same parity in order for the sum of their cubes to be
even. However, if they are both odd then u6 ≡ v 6 ≡ 1 mod 4, so u6 + v 6 6≡ 0 mod 8, a
contradiction. So we must have u = 2x, v = 2y for natural numbers x and y. But then
8(s6 + t6 ) = u6 + v 6 = 64(x6 + y 6 ), yielding x6 + y 6 = 8(s6 + t6 ). So (x, y, s, t) is a second
solution to the Diophantine equation, and since x + y = (u + v)/2 < u + v, we have
x + y + s + t < s + t + u + v. This contradicts our choice of solution (s, t, u, v), so no such
solution exists.
Alternate solutions. The n = 8(s6 + t6 ) rabbit out of a hat in the “official” solution
above isn’t the only way to solve this problem. Here are some alternate solutions.
Multiplying by 64. Suppose that n = a2 + b2 = c3 + d3 , but that n cannot be expressed
as a sum of two sixth powers. Arguing as above we may show that 64n = (8a)2 +
(8b)2 = (4c)3 + (4d)3 cannot be expressed as a sum of sixth powers either: Again, if
64n = x6 + y 6 then x and y must have the same parity; if they are both odd, then
x6 + y 6 ≡ 2 mod 4, and if they are both even, then n is a sum of sixth powers. Thus,
it suffices to find a single solution. Ha Young Shin used this approach with the initial
solution 637 = 142 + 212 = 83 + 53 . It’s easy to check that this is not a sum of sixth
powers, because 2 × 26 = 128 < 637 < 729 = 36 .
Working mod seven. A sixth power is congruent to 0 or 1 mod 7, so a sum of two
sixth powers is congruent to 0, 1 or 2 mod 7. Thus, if we can find n such that n =
a2 + b2 = c3 + d3 and n is not congruent to 0, 1 or 2 mod 7, then n is not a sum of
sixth powers. Moreover (7k + 1)6 n is both a sum of squares and a sum of cubes, and is
congruent to n mod 7, so it’s not a sum of sixth powers either. Thus, it suffices to find
a single solution satisfying the conditions above. Tom Yan used this approach and found
370 = 73 + 33 = 32 + 192 ≡ 6 mod 7 as an initial solution.

5
 Manipulating a factorisation. Chiao Lin considered the factorisation

c3 + d3 = (c + d)(c2 − cd + d2 )
= (c + d) (c − d)2 + cd

= (c + d)(c − d)2 + (c + d)cd.

If c and d can be chosen such that c + d and cd are both squares then c3 + d3 will be
a sum of squares. This can be achieved by letting c = j 2 (j 2 + 1), d = j 2 + 1, giving
n = (j 2 + 1)3 (j 6 + 1). To complete the problem, we may restrict our attention to j odd.
Then n is even, so as above, if n = x6 + y 6 then x and y have the same parity. If they
are both odd then x6 + y 6 ≡ 2 mod 8, and if they are both even then 64 | x6 + y 6 , so we
might hope to show that the highest power of 2 dividing n lies between 2 and 26 . Indeed,
when j = 1 we have n = 16, so j ≡ 1 mod 32 gives n ≡ 16 mod 32 and we are done. (In
fact it turns out that (j 2 + 1)3 (j 6 + 1) ≡ 16 mod 32 for all odd j, so we needn’t restrict
to j ≡ 1 mod 32.)
Exploiting primes. Malcolm Granville found yet another family of solutions. There are
infinitely many primes of the form p = 4k + 1 (by Dirichlet’s Theorem, or otherwise),
and for such a prime p, theorems about sums of squares tell us that n = 2p3 is a sum
of two squares. The factorisation x6 + y 6 = (x2 + y 2 )(x4 − x2 y 2 + y 2 ) and the inequality
x4 − x2 y 2 + y 4 ≥ 41 (x2 + y 2 )2 can then be used to show that 2p3 is not a sum of sixth
powers.

8. (a) Let b, n > 1 be integers. Suppose that for each k > 1 there exists an integer ak such
that b − ank is divisible by k. Prove that b = An for some integer A.
(b) Does the conclusion still hold if we only know that for every prime p there is an
integer ap such that b − anp is divisible by p?
Solution: Let the prime factorisation of b be b = pα1 1 · · · pαs s , where the pi are distinct
primes. Our goal is to show that all the exponents are divisible by n, so that we may set
α /n α /n
A = p1 1 · · · ps s .
To this end, apply the condition with k = b2 . The number b − ank is divisible by b2 and
hence, for each 1 ≤ i ≤ s, it is divisible by p2α
i
i
> pαi as well. Therefore

ank ≡ b ≡ 0 (mod pαi i ),

and
ank ≡ b 6≡ 0 (mod pαi i +1 ).
This implies that the highest power of pi dividing ank is pαi i . Since ank is an nth power,
this implies that αi is divisible by n, as desired.
For the second part, let n = 8 and b = 16. Then x8 − 16 ≡ 0 (mod p) factors as

(x2 − 2)(x2 + 2)(x2 − 2x + 2)(x2 + 2x + 2) ≡ 0 (mod p).

If −1 is a square mod p then x2 + 2x + 2 = (x + 1)2 + 1 has a solution mod p; and if

it is not, then one of x2 ≡ 2 and x2 ≡ −2 must have a solution (using the fact that the

6
 Legendre symbol (x/p) is multiplicative — this means that the product of two quadratic
non-residues must be a quadratic residue). This shows that the conclusion does not hold
under the weaker condition on b.

9. Show that there are infinitely many pairs of distinct primes (p, q) such that p | (2q−1 − 1)
and q | (2p−1 − 1).
Solution: We’re looking for pairs of primes (p, q) such that the order of 2 modulo p
divides q − 1, and the order of 2 modulo q divides p − 1. To do so, it’s obviously in our
interest to choose primes where we have some control over the multiplicative order of 2.
Consider a prime p dividing 2k + 1. We have 2k ≡ −1 mod p, and 22k ≡ (−1)2 ≡ 1 mod p,
so the order of 2 modulo p divides 2k but not k. We can control this completely if we
choose k of the form k = 2n , because then the order of 2 must equal 2n+1 ; so, if p divides
n
Fn = 22 + 1, then 2 has order 2n+1 modulo p.
So, let p be a divisor of Fn , and q a divisor of Fm , with n < m. Then p and q are distinct
(otherwise the order of 2 mod p is equal to both 2n+1 and 2m+1 , a contradiction), and in
addition we have p | (2q−1 − 1): certainly 2n+1 divides 2m+1 , and 2m+1 must divide q − 1,
by Fermat’s theorem. So, it remains to show that we can choose m so that 2m+1 divides
p − 1. We already have 2n+1 |(p − 1) (again by Fermat’s theorem), so let’s try m = n + 1
— we’ll then by halfway there (so to speak).
One way we could show that 2n+2 divides p − 1 is to show that there’s an integer a such
that the multiplicative order of a mod p is 2n+2 . Now, we already know that 2 has order
2n+1 mod p, so if we can choose a such that a2 ≡ 2 mod p we’ll be done. It’s known that
2 is a square mod p if and only if p ≡ ±1 mod 8 (this is “Supplement II” to the Law of
Quadratic Reciprocity); and since 2n+1 | (p − 1), such an a exists provided we restrict
ourselves to n ≥ 2.
In summary: if p and q are primes dividing Fn and Fn+1 respectively, with n ≥ 2, then p
and q are distinct and satisfy the conditions of the problem. Moreover, the first sentence
of the second paragraph shows that we get a different pair (p, q) for each n. This completes
the proof.

February 2010
www.mathsolympiad.org.nz