Author |
Topic: n divides 3^n+4^n (Read 611 times) |
|
Ronno
Junior Member
Gender: 
Posts: 140
|
 |
n divides 3^n+4^n
« on: Sep 9th, 2009, 3:04am » |
 Quote  Modify
|
Prove that if n>1 and n divides 3^n+4^n then 7 divides n.
|
|
 IP Logged |
Sarchasm: The gulf between the author of sarcastic wit and the person who doesn't get it..
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: n divides 3^n+4^n
« Reply #1 on: Sep 9th, 2009, 3:39am » |
Quote Modify
|
| hidden: |
First note that 3n+4n is not divisible by 2 or 3, so neither is n. Let p > 3 be the smallest prime dividing n. Now p divides
3n+4n = 3n(1 + an),
where a = 4*3-1 mod p. Thus an = -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 a2 = 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.
|
|
|
IP Logged |
|
|
|
Ronno
Junior Member
Gender:
Posts: 140
|
|
Re: n divides 3^n+4^n
« Reply #2 on: Sep 9th, 2009, 3:59am » |
Quote Modify
|
My proof is slightly different after a^n=-1 (mod p)
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)
|
|
IP Logged |
Sarchasm: The gulf between the author of sarcastic wit and the person who doesn't get it..
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print