1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Eulers and Fermats Theorems Help

  1. Oct 26, 2007 #1
    1. The problem statement, all variables and given/known data

    I'm having a hard time solving two problems I've been looking at for a while, they both involve Eulers theorem and Fermat's Little Theorem, here they are:

    Let p ≡ 3 (mod 4 ) be prime. Show that x^2 ≡ -1 (mod p) has no solutions. (Hint: Suppose x exists. Raise both sides to the power (p - 1)/2 and use Fermat's theorem).

    The other problem is this:

    Let n = 84047 * 65497. Find x and y with x^2 ≡ y^2 (mod n) but x ≠(the symbol should be not congruent, couldn't find the symbol) +- (plus or minus) y mod n.

    I've been looking at these for 2 hours and I don't know how to solve these. Any ideas? If you show the solution, please explain how if possible, thanks!

    2. Relevant equations

    Fermats little theorem: a^p-1 ≡ 1 mod p if p is a prime and p does not divide a.

    [tex]\phi(pq)[/tex] = (p -1)(q - 1) when n = pq and p and q are two distinct primes.

    3. The attempt at a solution

    For the first one, I took both sides to the power of (p - 1)/2 and got....

    x^p-1 ≡ 1 mod p

    The reason the -1 goes to 1 is because (p - 1)/2 must be even since p is prime, there -1 raised to an even power goes to 1. From this point on I don't know what to do, I tried making the claim that LaTeX graphic is being generated. Reload this page in a moment. x^p-1 was a in Eulers theorem and using his theorem and showing it was wrong, thus making the whole argument above wrong, but it did in fact work anyway....unless I did something wrong.

    For the 2nd problem, I don't know where to begin
  2. jcsd
  3. Oct 27, 2007 #2


    User Avatar
    Science Advisor
    Homework Helper

    Are you sure (p-1)/2 is even? We're given that p=3(mod4), i.e. p=4k+3.

    For the second problem, maybe try experimenting with a smaller n.
    Last edited: Oct 27, 2007
  4. Oct 27, 2007 #3
    Given that p = 4k + 3, wouldn't p have to be an odd? Anything a multiple of 4 is even, +3 will always result in an odd right? (even plus an odd is always an odd).
  5. Oct 27, 2007 #4
    Oh nevermind, an even divided by an even can be even or odd, its an even * even that is always even. So now, I get the following::

    x^p-1 ≡ -1 mod p

    which isn't right because fermat stated:

    x^p-1 ≡ 1 mod p

    so x^2 ≡ -1 mod p has no solutions

    man I suck.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook