3
$\begingroup$

I have this problem assigned as homework and I think I've proven it, but I'm not sure about one part of my proof.

For $n>1$, $a\in\mathbb{Z}$, $\gcd(a,n)=1$, and $o_n(a)=m$, if $ab\equiv 1\pmod{n}$ for $b\in\mathbb{Z}$, show $o_n(b)=m$.[Where $o_n(a)$ is the least positive integer $x$ for which $a^x\equiv 1\pmod n$].

Proof

$ab\equiv 1\pmod{n}\implies (ab)^m\equiv1^m\pmod{n}\implies a^mb^m\equiv 1\pmod{n}$.

But $o_n(a)=m\implies a^m\equiv 1\pmod{n}$, so $a^mb^m\equiv a^m\pmod{n}$. Since $\gcd(a,n)=1$, we have $\gcd(a^m,n)=1$, so we can divide both sides by $a^m$, giving $b^m\equiv 1\pmod{n}$.

Now, suppose that $b^t\equiv 1\pmod{n}$, some $0<t<m$. Then, $ab\equiv 1\pmod{n}\implies (ab)^t\equiv 1^t\pmod{n}\implies a^tb^t\equiv 1\equiv b^t\pmod{n}$. But, dividing both sides by $b^t$ yields $a^t\equiv 1\pmod{n}$, which contradicts $o_n(a)=m$. (This is the part I'm not sure about because I don't know if I can divide both sides by $b^t$ since it's not said anywhere that $\gcd(b,n)=1$.)

Hence, $o_n(b)=m$.

$\endgroup$
  • $\begingroup$ If $ p|b $ and $p|n$ then $p|ab$ and $p|(ab-1)$ ..(because $ ab-1\equiv 0 \pmod n$ implies that $ab-1$ is a multiple of $ n$) .But then $p|(ab-(ab-1)=1$. So gcd $(n,b)=1.$ $\endgroup$ – DanielWainfleet Nov 2 '15 at 3:58
  • $\begingroup$ I had to study your proof to find what $o_n(a)$ is. It's the least positive integer $x$ such that $a^x\equiv 1 \pmod n$. So I added the def'n to the Q. $\endgroup$ – DanielWainfleet Nov 2 '15 at 4:00
1
$\begingroup$

Once you have $a^mb^m\equiv 1 \pmod n$ and $a^m\equiv 1 \pmod n $, you have $b^m\equiv b^m.1\equiv b^ma^m\equiv 1\pmod n$. So $o_n(b)\leq m$.But if $o_n(b)=k $ for $0<k<m$ then $1\equiv ab \implies 1\equiv (ab)^k\equiv a^kb^k \equiv a^k.1\equiv a^k$ ,contradicting $o_n(a)=m.$...... One way to look at this Q is that multiplication modulo $n$ on the members of $\{1,...,n-1\}$ that are co-prime to $n$ is a finite commutative group with identity $1$. In ANY group, if the order of $a$ (the least positive $x$ for which $a^x=1$) exists and is equal to $m$ then the order of $a^{-1}$ is also $m$.

$\endgroup$
  • $\begingroup$ Oh ok, I hadn't thought of simply substituting into $a^kb^k\equiv 1$... Thanks for clearing it up! $\endgroup$ – MathQuestion Nov 2 '15 at 4:27

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.