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

- April 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*. - April 30th 2008, 11:46 AMtopsquark
- April 30th 2008, 12:33 PMPaulRS
2. for some natural number and for some natural number (a and b are quadratic residues modp)

Multiplying:

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,

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)