1
$\begingroup$

Let $a,b,q,m$ positive integers. Assume that $ab\equiv 1\pmod{m}$. Is it true that $a^q\not\equiv 0\pmod{m}$?

My approach: If $a^q\equiv 0\pmod{m}$, then $a^qb\equiv 0\pmod{m}$ and so $0\equiv aba^{q-1}\equiv a^{q-1}\pmod{m}$ and so, iteratively, $a\equiv 0\pmod{m}$, which contradicts that $ab\equiv 1\pmod{m}$.

Is this correct? Is there a more immediate way to see that the above claim must be true?

$\endgroup$
1
$\begingroup$

I would do it this way since it is very straightforward. For any integer $q$, we must have $$(ab)^q \equiv a^q b^q \equiv 1 \mod m.$$ If $a^q \equiv 0$, then we can write the above as $$0 = 0 b^q \equiv 1 \mod m,$$ which is a contradiction. So we can't have $a^q \equiv 0 \mod m$.

$\endgroup$
  • $\begingroup$ Yes, that's a more immediate way, thanks. $\endgroup$ – user144248 Aug 17 '14 at 22:11
1
$\begingroup$

With $ab\equiv 1 \pmod{m}$, we get $(ab)^q\equiv 1 \pmod{m}$. If $a^q \equiv 0 \pmod{m}$. This would imply $1 \equiv 0 \pmod{m}$. That is a contradiction.

$\endgroup$
  • $\begingroup$ Thanks, though it's the same answer as nayrb's. $\endgroup$ – user144248 Aug 17 '14 at 22:12
1
$\begingroup$

The thing is, with your assumption you already know that $(a,m)=1$ as integers. Hence, by the fundamental theorem of arithmetic you may never have $a^q \equiv 0 (\mod m)$, i.e. $m$ may never divide a power of $a$ because they have no common factors.

Hope this helps.

$\endgroup$
0
$\begingroup$

The conclusion heavily depends on $m$. All answes are pretty good, but they all overlooked one "tricky" case. What if $m=1$, since $1 \in \mathbb{N}$? If $m \not= 1$, then the conclusion is true, as other users have already proven, but if $m = 1$, then the conclsuion is wrong.

You need to be aware of cases like this, which are easy to overlook, especially if you are participating in contests or on exams, because the author of the problem intentionally puts them into the problem, just to check your awareness, since if you don't overlook that particular case, it's pretty forward to do it. Otherwise, you may face point deduction.

P.S. To be fair working with respect to modulo 1, doesn't make much sense, but as I've said sometimes you need to be aware of it.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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