Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Eulers and Fermats Theorems Help

  1. Oct 26, 2007 #1
    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!
    Last edited: Oct 26, 2007
  2. jcsd
  3. Oct 26, 2007 #2
    Notice that [tex]x^2 = -1[/tex] since [tex](p-1)/2[/tex] is an integer we can raise both sides to that power giving [tex]x^{p-1} = - 1[/tex] which is impossible because [tex]x^{p-1} = -1[/tex].
  4. Oct 26, 2007 #3
    I'm not sure I understand what you are saying. I did raise the both sides to the (p-1)/2 and I got this:

    [tex]x^{p-1}[/tex] ≡ 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 [tex]x^{p-1}[/tex] 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.
  5. Oct 26, 2007 #4
    I think it has to do with the fact that (p-1)/2 is odd when p=3 (mod 4), so (-1)^( p(-1)/2 ) = -1. Kummer meant "which is impossible because x^(p-1) = 1 (mod p)".
  6. Oct 27, 2007 #5
    How can (p - 1) / 2 be odd if p is prime? All prime numbers are odd, so minus one from an odd is an even, divided by 2 is another even.

    Or, are you saying the whole expression (p ≡ 3 mod 4) is a prime, and not p by itself? In that case, I don't understand....
  7. Oct 27, 2007 #6
    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
  8. Nov 11, 2007 #7

    Gib Z

    User Avatar
    Homework Helper

    6 divided by 2 doesn't look too even to me.
  9. Nov 17, 2007 #8
    Riemann Hypothesis

    what are trivial zeros?im a physics student and i'm willing to solve riemanns hypothesis.can you please simplify it's meaning...
  10. Nov 18, 2007 #9

    Gib Z

    User Avatar
    Homework Helper

    Lol well yes I'm willing to solve it as well, but thats somewhat harder to do than it sounds =] No offense, but I would cry if an Applied Mathematician, let alone a Physicist, let alone a physics student!! solved the Riemann Hypothesis. There are many equivalent statements that make the deep consequences of the theorem more evident, but in its original form it states that All the Non-trivial zeros of the Riemann Zeta function have a real part of 1/2.

    The Riemann Zeta function is defined for all complex numbers, [itex]z \neq -1[/itex] by the relation: [tex]\zeta (z) = \sum_{n=1}^{\infty} \frac{1}{z^n}[/tex]. The trivial zeros of the line are the negative even integers, so -2, -4, -6 etc etc. The Non trivial zeros are other values of z that zeta(z) = 0.
  11. Nov 26, 2007 #10
    grandnexus: 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.

    In those cases where x^2==y^2, Mod M it follows that (x-y)(x+y)==0. Mod M. So, simply by setting x==-y Mod M, we have a solution, such as x==1, y==-1 Mod M. BUT..

    In the case above, we are going to omit either solution, thus it must be that M has factors with both x+y and x-y. That is x-y =a, x+y = b, and M divides ab. For example a simple case is x=5, y=1, and X^2-Y^2 ==0 Mod 12.

    So the next step is to try and find those factors.
    Last edited: Nov 26, 2007
  12. Dec 24, 2007 #11
    because p ≡ 3 (mod 4 ) ==> p ≡ -1 (mod 4 ) ==> (p-1)/2 = odd, because p+1 are divisible by 4, which of course means that p-1 is not divisible by 4, only by 2

    the second problem: as robert said (x+y)(x-y)==0 mod n, but n do not divide x+y or x-y ==>

    ==> x+y = 84047, x-y = 65497 ==> x = 74772, y = 9275
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook