wu :: forums - Print Page


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

        riddles >> medium >> Prime power gcd
        
(Message started by: NickH on Mar 17^th, 2003, 3:55pm)

Title: Prime power gcd
Post by NickH on Mar 17^th, 2003, 3:55pm

Let p, m, and n be positive integers, with p an odd prime and m odd.

Show that gcd(p^m-1,pⁿ+1) = 2.

(gcd = greatest common divisor.)

Title: Re: Prime power gcd
Post by BNC on Mar 19^th, 2003, 3:36am

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...

Title: Re: Prime power gcd
Post by wowbagger on Mar 19^th, 2003, 4:14am

I don't think so.

Suppose p divides the gcd, so it divides p^m-1, too. However, p divides p^m (obviously), so it would have to divide 1 as well!?

Believe it or not, I can prove that
gcd (p^m-1, pⁿ+1) >= 2 ;)

Title: Re: Prime power gcd
Post by SWF on Mar 19^th, 2003, 5:42pm

If A(M)=p^M-1 and B(N)=p^N+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.

Title: Re: Prime power gcd
Post by NickH on Mar 24^th, 2003, 1:58pm

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.