Hey I am having trouble with this problem:



Not really sure how to use FLT to get a contradiction here

think i had a similar hw before lemme see if i can dig it up

Let p a prime number such that p = 3 [4].
Let x an integer such as x² = -1 [p].

Assume x is a multiple of p : so does x², and that's impossible since x² is not 0 [p].

Fermat's little theorem hence claims that : x^(p-1) = 1 [p].

Since p = 3 [4], p-1 = 2 [4] and (p-1)/2 = 1 [2].

Notice that :
x^(p-1) = (x²)^((p-1)/2)

Now we get :
(x²)^((p-1)/2) = 1 [p]
(-1)^((p-1)/2) = 1 [p]

But (p-1)/2 is an odd integer (see above) :
-1 = 1 [p]

p is an even prime : p = 2, and that's absurd because p = 3 [4].

I don't remember enough modular math to solve this, but I imagine you would have to assume that there exists an integer x such that x^2 is congruent to -1 mod p and then use FLT to say that x^p is congruent with x mod p. From there you'd need to use some mod rules to find that p cannot be congruent to 3 mod 4 and thus your assumption must be false.
So something like:
Given: p ≡ 3 mod 4
Assume: x^2 ≡ -1 mod p
FLT: x^p ≡ x mod p

From here you can start doing some stuff like take the last two and say that x^(p + 2) ≡ -x mod p and hence x^(p + 1) ≡ -1 mod p or x^(p + 3) ≡ 1 mod p or x^p * x^3 ≡ 1 mod p

I don't really know where to take it from here.

edit: I started typing before feanur posted :\

This post was edited by russian on Jan 28 2016 05:55pm

So after this point you get that gcd(x,p) = 1? Hence we can use FLT?

Since p is prime, gcd(x,p) = 1 or p.
If it's 1, FLT states that : x^(p-1) = 1 [p].
If it's p (ie : if x is a multiple of p), FLT only states that : x^p = x [p] (which is obvious).

I checked that gcd(x,p)=1 just to be able to use the strongest version of FLT.

Great, thank you!!