Results 1 to 2 of 2

Thread: Prove that GCD>1

  1. #1
    Senior Member
    Joined
    Nov 2007
    Posts
    329

    Prove that GCD>1

    We know that $\displaystyle n>1$ and $\displaystyle n|a^n-1$ ($\displaystyle a,n\in\mathbb{Z}^+$). Prove that $\displaystyle \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 $\displaystyle n>1$ and $\displaystyle n|a^n-1$ ($\displaystyle a,n\in\mathbb{Z}^+$). Prove that $\displaystyle \left(a-1;n\right)>1$.
    Here is a start. First now that $\displaystyle \gcd(a,n)=1$. And it is also safe to say that $\displaystyle n$ is odd.

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

    We can now prove this for prime powers. If $\displaystyle p^k|a^{p^k} -1$ it means $\displaystyle p|(a^{p^{k-1}})^p - 1$ using what we just proved it means $\displaystyle 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 $\displaystyle p|(a-1)$. Thus, certainly $\displaystyle \gcd(p^k,a-1)>1$.

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

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

    The last paragraph easily shows how we can generalize this argument for $\displaystyle 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 $\displaystyle 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: Mar 23rd 2010, 05:20 PM
  2. prove,,,
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Mar 1st 2010, 09:02 AM
  3. Prove |w + z| <= |w| +|z|
    Posted in the Algebra Forum
    Replies: 3
    Last Post: Feb 28th 2010, 05:44 AM
  4. Replies: 2
    Last Post: Aug 28th 2009, 02:59 AM
  5. How to prove that n^2 + n + 2 is even??
    Posted in the Algebra Forum
    Replies: 3
    Last Post: Nov 30th 2008, 01:24 PM

Search Tags


/mathhelpforum @mathhelpforum