Results 1 to 2 of 2

Thread: prime number

  1. #1
    Junior Member
    Joined
    Sep 2008
    Posts
    62

    prime number

    let p and q be distinct odd prime numbers with p-1 divides q-1. If a is with in integers with (a,pq)=1 prove that a^q-1=1mod pq
    Last edited by rmpatel5; Sep 23rd 2008 at 08:07 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    Quote Originally Posted by rmpatel5 View Post
    let p and q be distinct odd prime numbers with p-1 divides q-1. If a is with in integers with (a,pq)=1 prove that a^q-1=1mod pq
    let $\displaystyle q-1=d(p-1).$ since $\displaystyle \gcd(a,q)=1,$ we have $\displaystyle a^{q-1} \equiv 1 \mod q.$ also since $\displaystyle \gcd(a,p)=1,$ we have: $\displaystyle a^{p-1} \equiv 1 \mod p,$ which gives us: $\displaystyle a^{q-1}=(a^{p-1})^d \equiv 1 \mod p.$

    so we showed that both $\displaystyle p$ and $\displaystyle q$ divide $\displaystyle a^{q-1}-1,$ and thus $\displaystyle pq$ must also divide $\displaystyle a^{q-1} - 1. \ \ \ \square$
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 0
    Last Post: Sep 24th 2011, 11:23 AM
  2. Prime number 2
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: May 1st 2010, 04:03 AM
  3. Prime number
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: May 1st 2010, 03:53 AM
  4. Replies: 1
    Last Post: Sep 2nd 2009, 08:31 AM
  5. Number theory, prime number
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Sep 17th 2006, 08:11 PM

Search Tags


/mathhelpforum @mathhelpforum