quadratic residue...

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

2. Ifpis a prime number and bothaandbare quadratic residues modp, prove thatab(modp) is also a quadratic residue modp.

Printable View

- Apr 30th 2008, 11:12 AMmemb3rmenumber theory proof
quadratic residue...

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 AMtopsquark
- Apr 30th 2008, 12:33 PMPaulRS
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 - May 1st 2008, 09:41 AMmemb3rme
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 AMMoo
Hello,

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

Is it clearer ? :) - May 1st 2008, 11:04 AMIsomorphism
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)}$