• Sep 12th 2006, 10:56 AM
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 (:
• Sep 12th 2006, 02:03 PM
topsquark
Quote:

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
• Sep 12th 2006, 04:39 PM
ThePerfectHacker
If you are interesting in this...
Switch the topic from non-residue to residue
---
• Sep 13th 2006, 01:11 AM
Red_Fox
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.

(:
• Sep 13th 2006, 08:32 AM
ThePerfectHacker
Quote:

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!
• Sep 13th 2006, 11:34 AM
Red_Fox
yeah (:
:D
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