# Math Help - 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 (:

2. 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

3. If you are interesting in this...
Switch the topic from non-residue to residue
---

4. ## Well...

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.

(:

5. 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!

6. ## yeah (:

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