Results 1 to 2 of 2

Math Help - Prove that GCD>1

  1. #1
    Senior Member
    Joined
    Nov 2007
    Posts
    329

    Prove that GCD>1

    We know that n>1 and n|a^n-1 ( a,n\in\mathbb{Z}^+). Prove that \left(a-1;n\right)>1.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by james_bond View Post
    We know that n>1 and n|a^n-1 ( a,n\in\mathbb{Z}^+). Prove that \left(a-1;n\right)>1.
    Here is a start. First now that \gcd(a,n)=1. And it is also safe to say that n is odd.

    First, start easy, say n=p, a prime. Then a^p \equiv 1( \bmod p), but a^{p-1}\equiv 1(\bmod p) by Fermat's little theorem. Thus, a^p \equiv a^{p-1}(\bmod p) \implies a \equiv 1(\bmod p)\implies p|(a-1). Thus, certainly \gcd(p,a-1)>1.

    We can now prove this for prime powers. If p^k|a^{p^k} -1 it means p|(a^{p^{k-1}})^p - 1 using what we just proved it means p|a^{p^{k-1}}-1\implies p|(a^{p^{k-2}})^p - 1\implies p|a^{p^{k-2}}-1, continuing we arrive at p|(a-1). Thus, certainly \gcd(p^k,a-1)>1.

    We will show now that if n=pq for two distinct primes then it works too, more specifically p|a-1 or q|a-1. Say, pq|a^{pq} - 1. Then it means p|(a^q)^p -1 \mbox{ and }q|(a^p)^q - 1. Using the above results it means a^q\equiv 1(\bmod p) and a^p\equiv 1(\bmod q). If the order of a mod p is 1 the argument is complete, similarly if the order of a mod q is 1 the argument is complete. Thus, we can assume the order of a mod p and q is not 1. But since a^q \equiv 1(\bmod p) it means the order must be q (since the order divides q). Similarly since a^p \equiv 1(\bmod q) it means the order of a must be p. But since a^{p-1}\equiv 1(\bmod p) and a^{q-1}\equiv 1(\bmod q) it means (by properties of orders) that p|q-1 \mbox{ and }q|p-1. But this is impossible, for then p\leq q-1 and q\leq p-1 which would imply p\leq q-1\leq p-2 which is impossible.

    Now we can generalize this for n=pqr for three distinct primes. WLOG say p>q>r. If pqr|a^{pqr} - 1 then p|(a^{qr})^p -1 \mbox{ and }qr|(a^p)^{qr} -1. By using the above results it means a^{qr} \equiv 1(\bmod p) and a^p\equiv 1(\bmod q)\mbox{ or }a^p\equiv 1(\bmod r). If the order of a mod p or q or r is 1 then the proof is complete, i.e. p|(a-1)\mbox{ or }q|(a-1)\mbox{ or }r|(a-1). Thus it is safe to assume that the order of a mod any of those primes is greater than 1. Thus, the order of a mod r or q is p, WLOG say q, but then p|q-1\implies p\leq q-1\implies p<q which is impossible since we said p>q.

    The last paragraph easily shows how we can generalize this argument for n=p_1p_2...p_k for distinct primes by using induction.

    Thus, now we know it works for prime powers and distinct primes. We can think of n as a product of distinct primes and prime powers. This is the final step that remains.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Prove a/b and a/c then a/ (3b-7c)
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 23rd 2010, 06:20 PM
  2. prove,,,
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 1st 2010, 10:02 AM
  3. Prove |w + z| <= |w| +|z|
    Posted in the Algebra Forum
    Replies: 3
    Last Post: February 28th 2010, 06:44 AM
  4. Replies: 2
    Last Post: August 28th 2009, 03:59 AM
  5. How to prove that n^2 + n + 2 is even??
    Posted in the Algebra Forum
    Replies: 3
    Last Post: November 30th 2008, 02:24 PM

Search Tags


/mathhelpforum @mathhelpforum