Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
1  
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
add comment

3 Answers

up vote 8 down vote accepted

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

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

share|improve this answer
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. –  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
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. –  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
show 2 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.