Maths Olympiad Prep

Library / /13 of 22

Number theory Difficulty 8.4 Shortlist Prove it Germany

Problem:

Determine all positive integers kk and nn with the following property:
The number k4+n2k^{4}+n^{2} is divisible without remainder by the number 7k3n7^{k}-3^{n}.

Solution

Solution:

The only solution pair is (k;n)=(2;4)(k ; n)=(2 ; 4). For every solution pair, k4+n2k^{4}+n^{2} and 7k3n7^{k}-3^{n} are integers, where 7k3n7^{k}-3^{n} need not necessarily be positive. Since 7k7^{k} and 3n3^{n} are odd, 27k3n2 \mid 7^{k}-3^{n} holds, and therefore 2k4+n22 \mid k^{4}+n^{2}. Hence kk and nn must be either both even or both odd. In the latter case k4+n22mod4k^{4}+n^{2} \equiv 2 \bmod 4 holds, whereas 7k3n(1)k(1)n0mod47^{k}-3^{n} \equiv(-1)^{k}-(-1)^{n} \equiv 0 \bmod 4. Therefore kk and nn are both even, and we set k=2ak=2 a resp. n=2bn=2 b with positive integers a,ba, b. It follows that 72a32b(2a)4+(2b)27^{2 a}-3^{2 b} \mid(2 a)^{4}+(2 b)^{2} and further 49a9b16a4+4b249^{a}-9^{b} \mid 16 a^{4}+4 b^{2}. Now 49a9b1a1b0mod849^{a}-9^{b} \equiv 1^{a}-1^{b} \equiv 0 \bmod 8, so 16a4+4b216 a^{4}+4 b^{2} must also be divisible by 8.

Therefore bb must be even and can be represented as b=2cb=2 c with a suitable positive integer cc. It follows that 72a92c=(7a+9c)(7a9c)16(a4+c2)7^{2 a}-9^{2 c}=(7^{a}+9^{c})(7^{a}-9^{c}) \mid 16(a^{4}+c^{2}). Since always 7a9c7^{a} \neq 9^{c} and both powers are odd, 7a9c2|7^{a}-9^{c}| \geq 2, so that 7a+9c8(a4+c2)7^{a}+9^{c} \mid 8(a^{4}+c^{2}) must hold.

Lemma 1: For all a4a \geq 4, 7a>8a47^{a}>8 a^{4}.

Proof by complete induction on aa:
For a=4a=4, 2401=74>844=211=20482401=7^{4}>8 \cdot 4^{4}=2^{11}=2048 is true. Now assume 7a>8a47^{a}>8 a^{4}.
Then 7a+1=77a>78a4=8(a+1)47a4(a+1)4>8(a+1)47(45)4>8(a+1)47^{a+1}=7 \cdot 7^{a}>7 \cdot 8 a^{4}=8(a+1)^{4} \cdot \frac{7 a^{4}}{(a+1)^{4}}>8(a+1)^{4} \cdot 7 \cdot\left(\frac{4}{5}\right)^{4}>8(a+1)^{4}.

Lemma 2: For all c1c \geq 1, 9c>8c29^{c}>8 c^{2}.

Proof by complete induction on cc:
For c=1c=1, 9>89>8 is true. Now assume 9c>8c29^{c}>8 c^{2}. Then
9c+1=99c>98c2=8(c+1)29c2(c+1)2>8(c+1)29(12)2>8(c+1)29^{c+1}=9 \cdot 9^{c}>9 \cdot 8 c^{2}=8(c+1)^{2} \cdot \frac{9 c^{2}}{(c+1)^{2}}>8(c+1)^{2} \cdot 9 \cdot\left(\frac{1}{2}\right)^{2}>8(c+1)^{2}.

From the lemmas it follows that for a4a \geq 4, because of 7a+9c>8(a4+c2)7^{a}+9^{c}>8(a^{4}+c^{2}), no required numbers kk and nn exist. So only a=1,2,3a=1,2,3 still need to be examined.

Lemma 3: For all c3c \geq 3, 9c>305+8c29^{c}>305+8 c^{2}.

Proof by complete induction on cc:
For c=3c=3, 93=729>305+832=3779^{3}=729>305+8 \cdot 3^{2}=377 is true. Now assume 9c>305+8c29^{c}>305+8 c^{2}. Then 9c+1>9(305+8c2)=305+8(305+9c2)9^{c+1}>9\left(305+8 c^{2}\right)=305+8\left(305+9 c^{2}\right). Because of
305+9c2=(c+1)2+8c22c+304>(c+1)2+c(c2)>(c+1)2305+9 c^{2}=(c+1)^{2}+8 c^{2}-2 c+304>(c+1)^{2}+c(c-2)>(c+1)^{2} for c>2c>2, the claim follows.

Case 1: a=1a=1. For c=1c=1, 4981=3232=16(1+1)49-81=-32 \mid 32=16(1+1) holds. Therefore (k;n)=(2;4)(k ; n)=(2 ; 4) is a solution. For c=2c=2, 7+81=888(1+4)=407+81=88 \nmid 8(1+4)=40 holds. For c>2c>2, 7+9c8+8c27+9^{c} \leq 8+8 c^{2} must hold, hence 9c<1+8c29^{c}<1+8 c^{2}. This contradicts Lemma 3.

Case 2: a=2a=2. For c=1c=1, 72+91=587^{2}+9^{1}=58 and 8(24+12)=1368\left(2^{4}+1^{2}\right)=136 hold. For c=2c=2, 49+81=1308(16+4)=16049+81=130 \nmid 8(16+4)=160 holds. For c>2c>2, 49+9c8(16+c2)49+9^{c} \leq 8\left(16+c^{2}\right) must hold, hence 9c79+8c29^{c} \leq 79+8 c^{2}. This contradicts Lemma 3.

Case 3: a=3a=3. For c=1c=1, 343+9=352343+9=352 and 656=8(34+1)656=8\left(3^{4}+1\right) hold. For c=2c=2, 343+81=424343+81=424 and 680=8(34+4)680=8\left(3^{4}+4\right) hold. For c>2c>2, 343+9c8(81+c2)343+9^{c} \leq 8\left(81+c^{2}\right) must hold, hence 9c305+8c29^{c} \leq 305+8 c^{2}. This contradicts Lemma 3.

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 translated into English from de; metadata (topic, difficulty) added by this project.