1. ## number theory proof

1. Prove that is x^2 = a(mod n), then (n-x)^2 = a(mod n)

2. If p is a prime number and both a and b are quadratic residues mod p, prove that ab(mod p) is also a quadratic residue mod p.

2. Originally Posted by memb3rme

1. Prove that is x^2 = a(mod n), then (n-x)^2 = a(mod n)
$\displaystyle (n - x)^2 \equiv n^2 - 2nx + x^2~\text{(mod n)}$

$\displaystyle \equiv 0^2 - 2 \cdot 0 \cdot x + a~\text{(mod n)}$

$\displaystyle \equiv a~\text{(mod n)}$

-Dan

3. 2. $\displaystyle x^2\equiv{a}(\bmod.p)$for some natural number $\displaystyle x$ and $\displaystyle y^2\equiv{b}(\bmod.p)$for some natural number $\displaystyle y$ (a and b are quadratic residues modp)

Multiplying: $\displaystyle x^2\cdot{y^2}=(x\cdot{y})^2\equiv{a\cdot{b}}(\bmod .p)$

Thus a·b must be a quadratic residue

4. Quote:

1. Prove that is x^2 = a(mod n), then (n-x)^2 = a(mod n)

Ummm.... I don't understand where does the zero comes from......
SO assume that n is zero?..
some clarification here plz...

5. Hello,

$\displaystyle n \equiv 0 (mod \ n)$

Is it clearer ?

6. Originally Posted by memb3rme
Quote:
Ummm.... I don't understand where does the zero comes from......
SO assume that n is zero?..
some clarification here plz...
It is not that n is 0!
But n belongs to the equivalence class of 0. Put in layman terms, when we are seeing only remainders, n leaves the same remainder as 0 when they are divided by n, so they are equivalent.

To prove that directly from definition(if you are new to congruences)

$\displaystyle n|n(n-2x) \Rightarrow n|(n-x)^2 - x^2 \Rightarrow (n - x)^2 \equiv x^2 ~\text{(mod n)}$