help with abstract algebra please?

Question

suppose n is a prime number (not equal to 2 or 5). suppose X is a random number. n divides X^2 - 5. prove that n has to be ≡ to 1 mod 5 or 4 mod 5.

Answer 1

You need to know Gauss's quadratic reciprocity law to solve this exercise. Let p be a prime number and a be a number coprime to p. Then we write (a/p)=1 if a is congruent to a square modp, namely if there is an integer x so that p|a-x^2. If this is not the case, then we write (a/p)=-1.

Gauss' quadratic reciprocity law: If p and q are two different odd prime numbers, then (p/q)(q/p)=(-1)^{(p-1)(q-1)/4}.

Apply this to the exercise: set p=n and q=5. Since n|x^2-5, you have that (5/n)=1. Hence

(n/5)=(-1)^{n-1}=1, since n-1=even (n is a prime different from 2).

Therefore, n is congruent to a square mod5. It is really easy to check that the only integers that satisfy this property are the ones congruent to 1 or 4 (mod5), which completes the proof.

Check the site below for a better illustration of the gauss's law.

Answer 2

if X is a random number, n is prime,
and n | (X^2 - 5) then n ≡ 1. If n is any other prime, X can no longer be a random number.