Results 1 to 2 of 2

Math Help - 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; September 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 q-1=d(p-1). since \gcd(a,q)=1, we have a^{q-1} \equiv 1 \mod q. also since \gcd(a,p)=1, we have: a^{p-1} \equiv 1 \mod p, which gives us: a^{q-1}=(a^{p-1})^d \equiv 1 \mod p.

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

Similar Math Help Forum Discussions

  1. Replies: 0
    Last Post: September 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: September 2nd 2009, 08:31 AM
  5. Number theory, prime number
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 17th 2006, 08:11 PM

Search Tags


/mathhelpforum @mathhelpforum