×

# Residue Classes

Consider the diophantine equation -

$$x^3 + y^4 = 7$$

The solution which was given in the book had argument starting like - "Consider the residue class of $$x^3$$ modulo 13"

From where does one get motivation to check the residue class of that particular modulo?

Easy ones can be seen directly like checking residue class of modulo 3 in case of squares, modulo 7 in case of cubes, but what about others?

And yes, is there any list available of frequently used residue classes of modulo x? I think that might help many students. :)

Note by Soham Chanda
3 years, 8 months ago

## Comments

Sort by:

Top Newest

You are looking for prime numbers that have a lot of cube roots and fourth roots of unity. Modulo $$13$$, there are $$3$$ cube roots of unity ($$1,3,9$$) and $$4$$ fourth roots of unity ($$1,5,8,12$$), and so there are exactly $$4$$ cubes and $$3$$ fourth powers modulo $$13$$. This cuts down the number of possible residues of $$x^3+y^4$$ down to size (and, specifically, misses $$7$$, even if that is the only residue that gets missed out). · 3 years, 8 months ago

Log in to reply

Great explanation! To expand slightly, the primitive element theorem tells us that modulo $$p$$ there is a multiplicative generator $$g$$, such that the order of $$g$$ is $$p-1$$. Hence, we would have 3 cube roots if and only if $$p-1$$ is a multiple of 3. (Otherwise, there is only 1 cube root, namely 1.) In turn, this implies that there are $$\frac{p-1}{3}$$ possible values of cubes (and otherwise, there are $$p-1$$ values).

And if 13 didn't work, what would be the next number we try, given the same motivation? Staff · 3 years, 8 months ago

Log in to reply

$$37$$, being the next prime of the form $$12n+1$$. · 3 years, 8 months ago

Log in to reply

I think for cubes always check modulo 7,9, and 13 because the cubes leave very less numbers of distinct remainders modulo these numbers. · 3 years, 8 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...