Finding Perfect Squares Modulo a Number: 4 (mod 10) Example

[daster]

How do I find out if a number is a perfect square modulo a? For example, is 4 (mod 10) a perfect square?

 

[TenaliRaman]

An integer num is called a perfect square modulo a if num = foo^2 mod a for some integer foo.

4 = 4(mod 10) so go figure!

-- AI

 

[daster]

How about if we have something bigger, like 5 (mod 1234). How can we figure that out?

Also, does the same apply to perfect cubes?

 

[TenaliRaman]

There is no straight forward method. You have to try all numbers and if there is a number foo such that 5 = foo^2(mod 1234), you are done.(I would simply write up a small program and finish it off. Note that you will find foo between 0 and 1234, you don't have to look beyond).

These numbers are also called quadratic residues.
http://mathworld.wolfram.com/QuadraticResidue.html
There is a method given to find quadratic residue for (mod p) where p is prime.

And ofcourse there are also cubic residues.
http://mathworld.wolfram.com/CubicResidue.html

-- AI

 

[mathwonk]

well in the first place, you never lose the property of being a perfect square by modding out. so since 4 is a perfect square in the integers 4 = 2^2, it willk always be a perfect square modulo any integer. so that one question was a little naive.

then as to other more interesting cases like 5 mod 1234, i think there is a theory due to gauss which cuts the problem in half, at least when perhaps prime moduli are involved? called quadratic reciprocity. i.e. one number is a square modulo another if and only if the other is (or sometimes is not) a square modulo the other?

check this out. it is a major result. but higher degree problems do not enjoy the symmetry and simplicity of squaring problems.

here is the reciprocity theorem from one of the sites given above:

Number Theory Reciprocity Theorems


Quadratic Reciprocity Theorem

Also called the aureum theorema (golden theorem) by Gauss. If p and q are distinct odd primes, then the congruences
x^2 cong to p (mod q) and x^2 cong to q (mod p)

are both solvable or both unsolvable unless both p and q leave the remainder 3 when divided by 4 (in which case one of the congruences is solvable and the other is not).

thus for example, since 29 is congruent to the square 4 mod 5, we have 29 is a square mod 5, so then 5 is also a square mod 29, without having to find the square root. in fact 11^2 = 121 = 5 + 4(29) is congruent to 5 (mod 29). so mod 29, 11 is a square root of 5.

then if we ask whether 5 is a square, not mod 1234, but mod half of that, say mod 617, then since 617 is cong to 2 mod 5, and since 2 is not a square mod 5, it follows that 5 is not a square mod 617. hence 5 cannot be a square mod 1234 either, so in fact there is a method for solving your original problem. i.e. if x satisfies x^2 = (1234)n + 5, then x also satisfies x^2 = (617)(2n) + 5. since the second equation has no solution, neither does the first.

there is no such trick known to me for solving cubic equations or higher degree ones. indeed the study of cubic equations is called the theory of elliptic curves and is a huge subject of study even today, with ramifications in the proof of fermat's last theorem.

 

[robert Ihnot]

For cubes, we have the situation that if p-1, representing the multiplicative group, is not divisible by 3, then the cubes are simply
a permutation of the group. Take the case for p=5, there (1,2,3,4) each cubed Mod 5 gives (1,3,2,4) Mod 5.

 

[mathwonk]

daster, do you understand what he is saying? he is saying that if p is a prime, and 3 does not divide p-1, then every integer is a perfect cube mod p.

the reason is you look at the set of all cubes and then to say every number is a cube is equivalent to saying no two numbers have the same cube. but if two numbers have the same cube then their quotient has cube one. if a has cube one however and a≠1, then {a, a^2,1} froms a subgroup of order three of the group of non zero numbers mod p. but the order of subgroup divides the order of a group, so 3 must divide p-1.

for squares this condition is uninteresting since most primes p are odd, so 2 usually does divide p-1.

 

[daster]

Thanks for that!

I have another question.. Say we have the equation:
x^2 + 9y = 5, if we consider it modulo 9, does that give us:
x^2 = 5 (mod 9)?

If that's true, does it follow that there are no (x, y) integer solution pairs for the equation (since 5 isn't a prefect square modulo 9)?

 

[matt grime]

yes, that is correct.

 

[daster]

That's good to know. Thank you.