# How many residue classes satisfy the congruence $x^3 \equiv 3 \pmod{21}$?

How many residue classes satisfy the congruence $x^3 \equiv 3 \pmod{21}$?

I don't understand what this question is asking me to do.
Can someone simplify the question for me, thanks.

-
Given how many questions about modular arithmetic you are posting, have you considered at least trying to do a little markup on them? – Arturo Magidin Dec 6 '10 at 2:40
Why did you edited again the question after Arturo had kindly edited it so that it looks better? – Adrián Barquero Dec 6 '10 at 2:52
I edited it back because on my screen I am seeing [Math Processing Error] (in red font color) instead of the markup notation, sorry for all the confusion – fmunshi Dec 6 '10 at 3:08
alt-reload or shift-reload. It's not the mark-up or the site, it's your browser. – Arturo Magidin Dec 6 '10 at 3:27

The question is asking you to check which of the 21 residue classes of integers modulo $21$ (to wit, the class of $0$, the class of $1$, the class of $2$, etc) are solutions to $x^3\equiv 3\pmod{21}$. If nothing else occurs to you, you can certainly plug and chug and figure out which ones are solutions and which ones are not.

-

Just a little something to add to Arturo's answer. Note that any solution to $x^3\equiv 3 \pmod{21}$ will also be a solution to $x^3\equiv 3\pmod{3}$ and $x^3\equiv 3\pmod{7}$. So instead of checking all $21$ congruence classes, you can begin by checking the congruence classes modulo the prime powers of $21$. If one happens to have no solution, then modulo $21$ there should be no solution either. It should save you some time, as there are fewer classes to check.

This is an application of the following theorem.

Let $f(x)$ be a fixed polynomial with integral coefficients, and for any positive interger $m$, let $N(m)$ denote the number of solutions of the congruence $f(x)\equiv 0\pmod{m}$. If $m=m_1m_2$, where $gcd(m_1,m_2)=1$, then $N(m)=N(m_1)N(m_2)$. If $m=\prod p^\alpha$ is the canonical factorization of $m$, then $N(m)=\prod N(p^\alpha)$.

-
@yuone: i.e., a special case of the Chinese Remainder Theorem. I don't know what tools fmunshi has to analyze or study these kinds of equations, so I didn't want to tell him how to check, but you bring up a good point that one would not want to plug-and-chug one's way through all congruence classes. – Arturo Magidin Dec 6 '10 at 3:02
This is what I see on my screen: Just a little something to add to Arturo's answer. Note that any solution to [Math Processing Error] will also be a solution to [Math Processing Error] and [Math Processing Error]. So instead of checking all [Math Processing Error] congruence classes, you can begin by checking the congruence classes modulo the prime powers of [Math Processing Error]. If one happens to have no solution, then modulo [Math Processing Error] there should be no solution either. It should save you some time, as there are fewer classes to check. – fmunshi Dec 6 '10 at 3:10
@fmunshi, I don't know what to say, the answer seems to process fine for me. It could just be a temporary browser error, I've had it happen to me before. – yunone Dec 6 '10 at 3:22
@Arturo, please don't think that I meant your answer was deficient in anyway, quite the contrary! I just know with problems like these I tend to plug and chug, so I like to save time myself. – yunone Dec 6 '10 at 3:23
@fmunshi, @youone: you need to clear your cache and reload the interpreter. Hitting shift-reload or alt-reload usually fixes it for me. – Arturo Magidin Dec 6 '10 at 3:26

HINT $\rm\ \ mod\ 7:\ \ x^3 = 3\ \Rightarrow\ x^6 = \ldots\$ contra a well-known "little" theorem.

-