# Explain why $a^k\equiv1 \pmod {m_{1}\cdot m_{2}}$ if…

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

-
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

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

Also

$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

-
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