0
$\begingroup$

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

  • 0
    Also $n$ote 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.2012-10-08

1 Answers 1

0

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

  • 0
    Some $\LaTeX$ improvements: `\lcm` and `\gcd` for $\lcm,\gcd$; and `\mod` (also `\bmod,\pmod`) for $\mod m$.2012-10-12