Results 1 to 5 of 5

Math Help - Fermat, Congruences, the CRT, and an exam question

  1. #1
    Junior Member
    Joined
    Jun 2011
    Posts
    45

    Fermat, Congruences, the CRT, and an exam question

    Had the following problem on an exam, and couldn't crack it:

    Show that if p and q are primes, then p^(q-1) + q^(p-1) == 1 (mod pq)

    We know through Fermat each p^(q-1) == 1 (mod q) and q^(p-1) == 1(mod p). However I'm not sure how to combine the two.

    I thought the CRT might help if we changed the system to p^(q) == p(mod q) and q^(p) == q (mod p).

    If you think the problem easy, feel free to leave a hint rather than a solution so I have to work a bit -- I'd appreciate either
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Also sprach Zarathustra's Avatar
    Joined
    Dec 2009
    From
    Russia
    Posts
    1,506
    Thanks
    1

    Re: Fermat, Congruences, the CRT, and an exam question

    Quote Originally Posted by jsndacruz View Post
    Had the following problem on an exam, and couldn't crack it:

    Show that if p and q are primes, then p^(q-1) + q^(p-1) == 1 (mod pq)

    We know through Fermat each p^(q-1) == 1 (mod q) and q^(p-1) == 1(mod p). However I'm not sure how to combine the two.

    I thought the CRT might help if we changed the system to p^(q) == p(mod q) and q^(p) == q (mod p).

    If you think the problem easy, feel free to leave a hint rather than a solution so I have to work a bit -- I'd appreciate either

    From Fermat's theorem we get:

    p|q^{p-1}-1 and q|p^{q-1}-1

    Hence, pq|(q^{p-1}-1)(p^{q-1}-1).

    So...

    0\equiv(q^{p-1}-1)(p^{q-1}-1)=...

    Try to continue.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor chisigma's Avatar
    Joined
    Mar 2009
    From
    near Piacenza (Italy)
    Posts
    2,162
    Thanks
    5

    Re: Fermat, Congruences, the CRT, and an exam question

    Quote Originally Posted by jsndacruz View Post
    Had the following problem on an exam, and couldn't crack it:

    Show that if p and q are primes, then p^(q-1) + q^(p-1) == 1 (mod pq)

    We know through Fermat each p^(q-1) == 1 (mod q) and q^(p-1) == 1(mod p). However I'm not sure how to combine the two.

    I thought the CRT might help if we changed the system to p^(q) == p(mod q) and q^(p) == q (mod p).

    If you think the problem easy, feel free to leave a hint rather than a solution so I have to work a bit -- I'd appreciate either
    For the 'Fermat little theorem', if p and q are primes then...

    q|(p^{q-1}-1)

    p|(q^{p-1}-1) (1)

    Now is...

     (p^{q-1}-1)\ (q^{p-1}-1) = p^{q-1}\ q^{p-1} - p^{q-1}- q^{p-1}+1 (2)

    ... and from (1) and (2) You easily derive that...

    p\ q| (p^{q-1}+ q^{p-1}-1) (3)

    Kind regards

    \chi \sigma
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Jun 2011
    Posts
    45

    Re: Fermat, Congruences, the CRT, and an exam question

    Thanks so much, also sprach Zarathustra (didn't know that was the song's name until my latest google of your name) and ChiSigma. Sorry for not thanking earlier!
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor Also sprach Zarathustra's Avatar
    Joined
    Dec 2009
    From
    Russia
    Posts
    1,506
    Thanks
    1

    Re: Fermat, Congruences, the CRT, and an exam question

    Quote Originally Posted by jsndacruz View Post
    Thanks so much, also sprach Zarathustra (didn't know that was the song's name until my latest google of your name) and ChiSigma. Sorry for not thanking earlier!
    Now you just left to read Nietzsche...
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Question about Linear Congruences
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: June 18th 2011, 12:10 PM
  2. I think this question is on congruences and RSA
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 4th 2011, 01:35 AM
  3. Question about Linear Congruences
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: February 26th 2011, 11:09 AM
  4. another fermat's little theorem question
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: May 17th 2009, 10:14 AM
  5. Question involving congruences and gcd's
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 18th 2008, 05:23 PM

Search Tags


/mathhelpforum @mathhelpforum