0
$\begingroup$

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.

  • 0
    Given how many questions about modular arithmetic you are posting, have you considered at least trying to do a little markup on them?2010-12-06
  • 0
    Why did you edited again the question after Arturo had kindly edited it so that it looks better?2010-12-06
  • 0
    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 confusion2010-12-06
  • 1
    alt-reload or shift-reload. It's not the mark-up or the site, it's your browser.2010-12-06

3 Answers 3

8

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.

4

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

  • 2
    @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.2010-12-06
  • 0
    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.2010-12-06
  • 0
    @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.2010-12-06
  • 2
    @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.2010-12-06
  • 0
    @fmunshi, @youone: you need to clear your cache and reload the interpreter. Hitting shift-reload or alt-reload usually fixes it for me.2010-12-06
  • 0
    Does it process correctly now? If not, perhaps I'll just repost.2010-12-06
  • 0
    @yunone: It's not your post! The problem is at fmunshi's end. Reposting will not help him.2010-12-06
2

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