Problem A. 393. (February 2006)
A. 393. Prove that if n>1 is an integer such that 3^{n}+4^{n} is divisible by n then n is divisible by 7.
(5 pont)
Deadline expired on 16 March 2006.
The number 3^{n}+4^{n} is odd and not divisible by 3, therefore n is odd as well and not divisible by 3.
Write n=2k+1. Then
3^{n}+4^{n}=3^{.}9^{k}+4^{2k+1}3^{.}(1)^{k}1 (mod 5).
This number is not divisible by 5 for any value of n, so neither 5 is a divisor of n.
Let p be the smallest prime divisor of n and c is that residue class for which 4c3 (mod p). Then
4^{n}(c^{2n}1)=(c^{n}1)((4c)^{n}+4^{n})(c^{n}1)(3^{n}+4^{n})0 (mod p)
and
(1)  c^{2n}1 (mod p). 
By Fermat's theorem,
(2)  c^{p1}1!(mod p). 
Let d be the order of c modulo p. By (1) and (2), d is a common divisor of 2n and p1, so d is a divisor of their GCD which is 2. Therefore d2 and
pc^{2}1=(c+1)(c1).
If pc1 then 44c3 (mod p) which is a contradiction. So we have pc+1 and
04(c+1)=4c+43+4=7 (mod p).
This implies p=7.
Statistics:
