# Eulers and Fermats Theorems Help

1. Oct 26, 2007

### grandnexus

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.

$$\phi(pq)$$ = (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. Oct 27, 2007

### morphism

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
3. Oct 27, 2007

### grandnexus

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).

4. Oct 27, 2007

### grandnexus

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.