# number theory proof

• Apr 30th 2008, 11:12 AM
memb3rme
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.
• Apr 30th 2008, 11:46 AM
topsquark
Quote:

Originally Posted by memb3rme

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

$(n - x)^2 \equiv n^2 - 2nx + x^2~\text{(mod n)}$

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

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

-Dan
• Apr 30th 2008, 12:33 PM
PaulRS
2. $x^2\equiv{a}(\bmod.p)$for some natural number $x$ and $y^2\equiv{b}(\bmod.p)$for some natural number $y$ (a and b are quadratic residues modp)

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

Thus a·b must be a quadratic residue
• May 1st 2008, 09:41 AM
memb3rme
Quote:

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

http://www.mathhelpforum.com/math-he...5f5d0f91-1.gif

http://www.mathhelpforum.com/math-he...4d662e74-1.gif

http://www.mathhelpforum.com/math-he...3abf1b07-1.gif

Ummm.... I don't understand where does the zero comes from......
SO assume that n is zero?..
some clarification here plz...
• May 1st 2008, 09:46 AM
Moo
Hello,

$n \equiv 0 (mod \ n)$

Is it clearer ? :)
• May 1st 2008, 11:04 AM
Isomorphism
Quote:

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)

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