Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Supppose that $\gcd(m_{1},m_{2})=1$ and that for some $a$ and $k\ge1$ we have that $a^k\equiv1 \pmod{m_{1}}$ and that $a^k\equiv1\pmod{m_{2}}$. Explain why $a^k\equiv1 \pmod{m_{1}\cdot m_{2}}$.

share|cite|improve this question
The $a^k$ form is superfluous: one can just say $b\equiv1$ modulo $m_1$ and $m_2$ (where $b=a^k$) implies $b\equiv1$ mod $m_1m_2$. Note that $m_1,m_2\mid(b-1)$ so $\mathrm{lcm}(m_1,m_2)\mid(b-1)$, if it helps to see the problem in terms of divisibility statements. (I assume you are not at the level where you can utilize CRT.) – anon Oct 8 '12 at 19:41
Also note the downvote (though not from me): you've transcribed an exercise, and so in effect you've adopted the same tone of the exercise, which is essentially the position of you commanding us to do a problem for you. (And you haven't added any of your thoughts to the post: what you understand / don't understand, what you've tried, etc.) It's easy not to see how this comes across to others when you're new. – anon Oct 8 '12 at 19:43
up vote 0 down vote accepted

Relabel $a^k = a$ because the $k$ is quite irrelevant actually. (I think the OP is confused about Fermat's little and might want to study it again.)

Also relabel $m_1$ and $m_2$ as $b$ and $c$. ( I find that easier thats all )

We are given : $a = 1 $ $mod$ $ b$ and $a = 1 $ $mod$ $ c$

and $gcd(b,c) = 1$.

Thus $a = b x + 1$ and $a= c y + 1$ for some integer $b$ and $c$. It follows that $a-1 = b x = c y$. Thus $a-1$ is both divisible by $b$ and $c$.

$b,c | (a-1) => lcm(b,c) | (a-1).$


$lcm(b,c) | (a-1)$ and $gcd(b,c) = 1$ => $lcm(b,c) = bc$ ( because of unique prime factorization of any integer $> 1$ )

So $bc | (a-1).$

Hence $a-1 = b c z$ for some integer $z$ because $b$ and $c$ have no common divisor. Since $a-1 = b c z$ it must follow that $a = b c z + 1$ which is equivalent to $a = 1$ $ mod $ $bc$ QED

share|cite|improve this answer
The proof is incorrect or incomplete (hint: you did not employ one of the hypotheses, without which the result fails). For a correct proof, see anon's comment, posted 11 minutes prior (which it seems that - once again - you are following. If that is true then, as I mentioned before, one should give credit and flag the answer for CW status). – Bill Dubuque Oct 8 '12 at 20:57
No, the proof is not correct. You do need to employ some "gcd stuff" since, generally it is not true that $\rm\:b,c\:|\:a\!-\!1\:\Rightarrow\:bc\:|\:a\!-\!1$. – Bill Dubuque Oct 8 '12 at 21:18
Oh Im sorry. You are correct. – mick Oct 8 '12 at 21:22
Chloe : I edited. Bill was right. @Bill : Thanks. You are right. Im sorry. I edited. – mick Oct 8 '12 at 21:31
It uses $\rm\:b,c\:|\:n\:\Rightarrow\:lcm(b,c)\:|\:n,\:$ and $\rm\:gcd(b,c) = 1\:\Rightarrow\:lcm(b,c) = bc.\ \ $ CW means Community Wiki, which implies no rep changes from votes. – Bill Dubuque Oct 8 '12 at 21:36

Your Answer


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.