hints on this integer congruence problem?

Question

prove: if x^2 = n (mod 65) has a solution (for x), then x^2 = -n (mod 65) has a solution.

(the "=" are congruence symbols.)

Answer 1

Here's a hint:

The definition of congruence states that your two integers will be divisible by the modulus. For instance, (x-y)/m evenly means x=y (where = is a congruence symbol).


In your case,

(x^2 - n) will be divisible (evenly) by 65.

If that is solvable, then making the second number a negative, i.e. -n, makes the equation look as follows:

(x^2 - (-n)) / m ... And the negative signs cancel to give...

x^2 + n.

Now, if the original equation is divisible evenly when you subtract one unit of "n", then when you add one unit of "n", it will still be evenly divisible.

Let's use a concrete example: Let x=5 and n=1 (mod 2)

Prove: x^2 = n then x^2 = -n

(5^2 -1)/2 = 24/2 = 12 (so in this case congruence is maintained)
(5^2 - (-1)/2 = 26/2 = 13 (congruence is maintained).

Hope that helps.

Regards,

Mysstere