Algebra / Cryptography Questions?

Question

1. Let p be a prime. Show that the equation x^2 'is congruent to' 1 mod p has exactly two solutions in Zp, 1 and p - 1.

2. Consider Z13 = {1, 2, ..., 12}. The elements 2, 3, ..., 11 can be paried off with their inverses as follows
(2, 7), (3, 9), (4, 10), (5, 8), (6, 11)
Problem : Generalize this example to the case where p is any prime and show that
(p - 1)! 'is congruent to' -1 mod p
(This result is called Wilson's theorem).

3. Show that if p is prime
(p - 1)(p - 2) ... (p - r) 'is congruent to' (-1)^(r) * r! mod p
for each r = 1, 2, ..., p - 1.

4. Show that if p is prime
2(p - 3)! + 1 'is congruent to' 0 mod p

5. In 1732, Euler wrote "I derived [certain] results from the elegant theorem, of whose truth I am certain, although I have no proof : a^(n) - b^(n) is divisible by the prime n + 1 if neither a nor b is."
Use Fermat's theorem to help Euler out with a proof.

Am completely confused about all the questions - please show working! Thx

Answer 1

Q1. Suppose there exists x, such that: x^2 = 1 (mod p).

x^2 = 1
x^2-1 = 0
(x+1)(x-1) = 0

As we are working in a prime modulus, there are no zero divisors, which means that either x+1 = 0, or x-1 = 0. Thus, the only solutions for x are 1 and -1 (which is p-1).

Q2. (p-1)! = 1*2*3*...*(p-1)
Each number in the range 2 to (p-2) can be paired off with its reciprocal. None of these numbers are their own reciprocal by Q1. Also, each number has only one reciprocal (Suppose it had two. a*b = 1; a*c = 1. Then ab-ac = a(b-c) = 0. a is not zero, so b-c is 0, thus b and c are the same reciprocal). Thus, the product of 2*3*...(p-3)*(p-2) = 1.
(p-1)! = 1*(1)*(p-1) = p-1 = -1

Q3.

(p - 1)(p - 2) ... (p - r) = (-1)(-2)(-3)...(-r) = (-1)^r*(1)(2)(3)..(r) = (-1)^r*r!

Q4.

2(p - 3)! + 1 = -(p-2)(p-3)!+1 = -1(p-2)(p-3)!+1 = (p-1)(p-2)(p-3)!+1 = (p-1)!+1 = -1+1 = 0

Q5. By Fermat's little Theorem, with n+1 prime:
a^n = 1 (mod n+1)
b^n = 1 (mod n+1)

Thus, a^n-b^n = 1 -1 = 0 (mod n+1).
This means that (n+1) divides a^n-b^n.

Answer 2

Fermat's theorm is extremely difficult and only has been proven one way or the other in the last 15 years or so. Someone is throwing you a curve ball.