Eulers and Fermats Theorems Help

[grandnexus]

Homework Statement

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!

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

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

 

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

 

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

 

[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 pso x^2 ≡ -1 mod p has no solutionsman I suck.