Author |
Topic: Prime power gcd (Read 606 times) |
|
NickH
Senior Riddler
Gender: 
Posts: 341
|
 |
Prime power gcd
« on: Mar 17th, 2003, 3:55pm » |
 Quote  Modify
|
Let p, m, and n be positive integers, with p an odd prime and m odd.
Show that gcd(pm-1,pn+1) = 2.
(gcd = greatest common divisor.)
|
|
 IP Logged |
Nick's Mathematical Puzzles
|
|
|
BNC
Uberpuzzler
Gender:
Posts: 1732
|
|
Re: Prime power gcd
« Reply #1 on: Mar 19th, 2003, 3:36am » |
Quote Modify
|
Hey, I'm probably missing something, but won't p be a common divisor as well (possibly greater than 2)?
<later addition>
Oops, sorry! I thought the (+1) and (-1) are in the power...
|
| « Last Edit: Mar 19th, 2003, 1:23pm by BNC » |
IP Logged |
How about supercalifragilisticexpialidociouspuzzler [Towr, 2007]
|
|
|
wowbagger
Uberpuzzler
 
Gender:
Posts: 727
|
|
Re: Prime power gcd
« Reply #2 on: Mar 19th, 2003, 4:14am » |
Quote Modify
|
I don't think so.
Suppose p divides the gcd, so it divides pm-1, too. However, p divides pm (obviously), so it would have to divide 1 as well!?
Believe it or not, I can prove that
gcd (pm-1, pn+1) >= 2 
|
| « Last Edit: Mar 19th, 2003, 4:28am by wowbagger » |
IP Logged |
"You're a jerk, <your surname>!"
|
|
|
SWF
Uberpuzzler
Posts: 879
|
|
Re: Prime power gcd
« Reply #3 on: Mar 19th, 2003, 5:42pm » |
Quote Modify
|
If A(M)=pM-1 and B(N)=pN+1 are each multiples of a common divisor d>1, with M and N positive odd integers (not necessarily equal to the m and n in the orginal problem statement) then there are three possiblities:
- M=N: the common factor must be 2
- M>N: there is an odd positive integer j<M such that A(j) is a multiple of d
- N>M: there is an odd positive integer k<N such that B(k) is a multiple of d
If M>N, replace M by j and repeat, and if N>M, replace N by k and repeat. Lather, rinse, repeat until M=N at which point it has been shown that the common divisor must be 2.
Now to prove the above claims. Obviously 2 is a common divisor, and d is not a factor of p. This is tedious to type (and probably to read), so please forgive me for not formatting all the exponents to look nice.
If M=N: A(M)+B(N)= 2*p^M must be a multiple of d, and d is relatively prime to p, so d is 2.
If M>N: A(M)+B(N)=p^M+p^N=p^N*(p^(M-N)+1)=p^N*B(M-N) is a multiple of d and therfore so is B(M-N). Next find the difference between and B(N) and B(M-N) which is a multiple of d. N cannot equal M-N because N is odd and M-N is even. If N>M-N, B(N)-B(M-N)=p^(M-N)*A(2*N-M), and A(2*N-M) is a multiple of d with 0<2*N-M<M. If M-N>N, B(M-N)-B(N)=p^N*A(M-2*N), and A(M-2*N) is a mulitple of d with 0<M-2*N<M.
If N>M: A(M)+B(N)=p^M+p^N=p^M*(p^(N-M)+1)=p^M*B(N-M) is a multiple of d and therfore so is B(N-M). Next find the sum of A(M) and B(N-M) which is a multiple of d. M cannot equal N-M because M is odd and N-M is even. If M>N-M, A(M)+B(N-M)=p^(N-M)*B(2*M-N), and B(2*M-N) is a multiple of d with 0<2*M-N<N. If M<N-M, A(M)+B(N-M)=p^M*B(N-2*M), and B(N-2*M) is a mulitple of d with 0<N-2*M<N.
|
|
IP Logged |
|
|
|
NickH
Senior Riddler
Gender:
Posts: 341
|
|
Re: Prime power gcd
« Reply #4 on: Mar 24th, 2003, 1:58pm » |
Quote Modify
|
I realised that this result applies to any odd number, p > 1, not just to odd primes. A similar result applies to all positive even numbers -- there the gcd is 1. Quite a surprising result, I think.
|
| « Last Edit: Mar 24th, 2003, 1:59pm by NickH » |
IP Logged |
Nick's Mathematical Puzzles
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print