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

  • 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.)2012-10-08
  • 0
    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.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
    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).2012-10-08
  • 1
    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$.2012-10-08
  • 0
    Oh Im sorry. You are correct.2012-10-08
  • 0
    Chloe : I edited. Bill was right. @Bill : Thanks. You are right. Im sorry. I edited.2012-10-08
  • 0
    I do not know what CW status is.2012-10-08
  • 1
    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.2012-10-08
  • 0
    Hm yes you are right Bill. I consider that trivial but formally you are correct. It might help the OP. +12012-10-08
  • 0
    Anyways I did not read anon's comment and did thus not use it. Thus with all respect for you and him , I do not credit him.2012-10-08
  • 0
    Here what you call "gcd stuff" is the essence of the matter, so it is important to explicitly mention *why* you can make that inference. It need not hold true for slightly more general number systems, e.g. rings of quadratic integers $\rm\:a + b\sqrt{d},\:$ where unique factorization and related properties may fail.2012-10-08
  • 0
    Yes , I hesitated to mention unique factorization , but I feared the OP did not know that. Your comment of lcm does the job , but I cant steal it from you can I ? Im not sure if I made a solid formal proof , but at least I explained it. With unique factorization and your lcm comment the proof is completely formal.2012-10-08
  • 0
    At the OP and Bill , sorry for being sloppy.2012-10-08
  • 0
    Please feel welcome to add it to your answer.2012-10-08
  • 0
    Later , have to run.2012-10-08
  • 0
    I edited. I hope you approve.2012-10-12
  • 0
    Some $\LaTeX$ improvements: `\lcm` and `\gcd` for $\lcm,\gcd$; and `\mod` (also `\bmod,\pmod`) for $\mod m$.2012-10-12