×

# 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
4 years, 1 month ago

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

• bulleted
• list

1. numbered
2. list

1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

> This is a quote
This is a quote
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$...$$ or $...$ to ensure proper formatting.
2 \times 3 $$2 \times 3$$
2^{34} $$2^{34}$$
a_{i-1} $$a_{i-1}$$
\frac{2}{3} $$\frac{2}{3}$$
\sqrt{2} $$\sqrt{2}$$
\sum_{i=1}^3 $$\sum_{i=1}^3$$
\sin \theta $$\sin \theta$$
\boxed{123} $$\boxed{123}$$

Sort by:

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

- 4 years, 1 month ago

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 - 4 years, 1 month ago

$$37$$, being the next prime of the form $$12n+1$$.

- 4 years, 1 month ago

I think for cubes always check modulo 7,9, and 13 because the cubes leave very less numbers of distinct remainders modulo these numbers.

- 4 years, 1 month ago