Thread: quadratic residues

Hi everyone!
I need to refute the following:
the product of two numbers, which both are not a quadratic residue mod 35, is a quadratic residue mod 35.
in other words, to find a product of those numbers which is not a quadratic residue mod 35.

Thanks,
RedFox (:

Originally Posted by Red_Fox

Hi everyone!
I need to refute the following:
the product of two numbers, which both are not a quadratic residue mod 35, is a quadratic residue mod 35.
in other words, to find a product of those numbers which is not a quadratic residue mod 35.

Thanks,
RedFox (:

Well, it's not elegant, but it works.

I'm using the definition that q is a quadratic residue (mod 35) if there exists an integer x, 0 < x < 35, such that x^2 = q (mod 35).

So I made a list of all such possible q. (Simply take all possible 0<x<18, the list repeats itself backward for 17<x<36, and find q for each x.) I get that q = 1, 4, 9, 11, 14, 15, 16, 21, 25, 29, 30 are all quadratic residues (mod 35).

A counter-example is 2 and 3. Both 2 and 3 are not quadratic residues (mod 35) and neither is 2 x 3 = 6.

-Dan

If you are interesting in this...
Switch the topic from non-residue to residue
---
The product of two quadradic residues of a prime is again a quadradic residue of a prime. I made I comment about this some time ago on this forum when I realized the quadradic residues (in fact cubic, quartic, ...) residues form a group (which is why residue times residue is residue because it is closed) under multiplication modulo p. This leads us to some truly elegant results. For example, the number of quadradic,cubic,quartic,... residues always must divide p-1. I thought anyone who studied group and number theory might appreciate this because the results might be complicated to prove on an elementary level.

First, thank you very much!
Although as you said the proof is not so elegant, however, it works.
And about what you said - this is really interesting! I knew just about the number of quadradic residues - which is (p-1)/2. It's nice to see that for any "other" kind of residues (cubic,...) p-1 must divide the number of them.

(:

Originally Posted by Red_Fox

First, thank you very much!
Although as you said the proof is not so elegant, however, it works.

There is no general method of finding all quadradic residues of a prime. I belive the algorithm is NP-complete.
Therefore it is no suprise it is not elegant.


Let me tell you a rule for mathematcians: It is not how to find the solution it is to show the solution exists!

I've heard this a lot in our department...
I'm just finishing my B.A on applied math now, so maybe in the future I will do more things as "how to find the solution".....

TNX