Eulers and Fermats Theorems Help

[grandnexus]

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!

 

[Kummer]

Notice that $$x^2 = -1$$ since $$(p-1)/2$$ is an integer we can raise both sides to that power giving $$x^{p-1} = - 1$$ which is impossible because $$x^{p-1} = -1$$.

 

[grandnexus]

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:

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

 

[dodo]

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

 

[grandnexus]

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

 

[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

 

[Gib Z]

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.

6 divided by 2 doesn't look too even to me.

 

[Graviton]

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

 

[Gib Z]

Lol well yes I'm willing to solve it as well, but that's 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, $z \neq -1$ by the relation: $$\zeta (z) = \sum_{n=1}^{\infty} \frac{1}{z^n}$$. 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.

 

[robert Ihnot]

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.

 

[al-mahed]

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!

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