Re: Number with quadratic residue.

"mina_world" <mina_world@xxxxxxxxxxx> wrote:
mina_world <mina_world@xxxxxxxxxxx> wrote:

All quadratic residues mod 5 are 1, 4.
All quadratic residues mod 7 are 1, 2, 4.
All quadratic residues mod 35 are
1) a = 1 (mod 5), a = 1 (mod 7)
2) a = 1 (mod 5), a = 2 (mod 7)
3) a = 1 (mod 5), a = 4 (mod 7)
4) a = 4 (mod 5), a = 1 (mod 7)
5) a = 4 (mod 5), a = 2 (mod 7)
6) a = 4 (mod 5), a = 4 (mod 7)

By Chinese Remainder theorem,
so, All quadratic residues mod 35 are 1, 4, 9, 11, 16, 29.

But I can't understand that 1)~6) are quadratic residues mod 35.

If some "a" is a quadratic residue mod 35,
then x^2 = a (mod 35) for some solution x with (a, 35) = 1.
<==> x^2 = a (mod 5) and x^2 = a (mod 7) for same x.

Since a = 16 is quadratic residue mod 35 by 2),
x^2 = 16 (mod 35) for some solution x.
<==> x^2 = 16 = 1 (mod 5) and x^2 = 16 = 2 (mod 7) for same x.

But I can't guarantee "same x".
I only know that x^2 = 1 (mod 5) for some x and
x^2 = 2 (mod 7) for some x by quadratic residue assumption.

I found my answer. Let's go...
If there exists the solutions of x^2 = a (mod 5), x^2 = a (mod 7),
represent x = +- b (mod 5)), x = +- c (mod 7) respectively.

1) x = b (mod 5), x = c (mod 7)
2) x = b (mod 5), x = -c (mod 7)
3) x = -b (mod 5), x = c (mod 7)
4) x = -b (mod 5), x = -c (mod 7)

this is the solution of x^2 = a (mod 35)
Because, <==> x^2 = a (mod 5) and x^2 = a (mod 7)

Namely, If "a" is a quadratic residue mod 5 and mod 7,
then "a" is a quadratic residue mod 35.

Consider inverse. If "a" is a quadratic residue mod 35,
there exists the solutions of x^2 = a (mod 35).
<==> x^2 = a (mod 5) and x^2 = a (mod 7).
so, "a" is a quadratic residue mod 5 and mod 7.

As I hinted in my prior reply here, this is an immediate
consequence of the product decomposition Z/35 = Z/5 x Z/7
Recall operations are defined componentwise in products, so
(a,b) in A x B -> f(a,b) = (f(a),f(b)), any f(x) in Z[x]
So f(a,b) = 0 <-> f(a) = f(b) = 0. Thus the roots in
the product are precisely the product set of the roots
in each component. In your example f(x) = x^2 - c, so
the roots are simply the product set of the square roots
of c in each component. As you learn algebra it's essential
to shift from thinking elementwise to thinking structurally.
Else you'll forever struggle to see the forest for the trees.

--Bill Dubuque
.

Quantcast