wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> n divides 3^n+4^n
        
(Message started by: Ronno on Sep 9^th, 2009, 3:04am)

Title: n divides 3^n+4^n
Post by Ronno on Sep 9^th, 2009, 3:04am

Prove that if n>1 and n divides 3^n+4^n then 7 divides n.

Title: Re: n divides 3^n+4^n
Post by Eigenray on Sep 9^th, 2009, 3:39am

[hideb]
First note that 3ⁿ+4ⁿ is not divisible by 2 or 3, so neither is n. Let p > 3 be the smallest prime dividing n. Now p divides
3ⁿ+4ⁿ = 3ⁿ(1 + aⁿ),
where a = 4*3^-1 mod p. Thus aⁿ = -1 mod p, so if r is the order of a mod p, then r | 2n. And since r | p-1, we have r | gcd(2n,p-1). But because p is the smallest prime dividing n, n is relatively prime to (p-1)/2, so
gcd(2n, p-1) = 2 gcd(n, (p-1)/2) = 2.
Thus r | 2, meaning a² = 1 mod p. If a = 1 mod p, then 3 = 4 mod p, which is absurd. Therefore a = -1 mod p, and 3 = -4 mod p, and so p = 7 divides n as required.
[/hideb]

Title: Re: n divides 3^n+4^n
Post by Ronno on Sep 9^th, 2009, 3:59am

My proof is slightly different after [hide]a^n=-1 (mod p)[/hide]

[hide]Since n is odd, (-a)^n=1 (mod p)
Let r be the order of -a mod p. Then r divides n and r divides p-1, implying r<p. So, by definition of p, r=1.
Then -a=1 (mod p) and hence 3=-4 (mod p)[/hide]