• Sep 12th 2006, 11: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, 03: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, 05:39 PM
ThePerfectHacker
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.
• Sep 13th 2006, 02: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, 09: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, 12:34 PM
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