# Number Theory: Show that $o_n(b)=m$ if $o_n(a)=m$ and $ab\equiv 1\pmod{n}$

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

• 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.$ – DanielWainfleet Nov 2 '15 at 3:58
• 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. – DanielWainfleet Nov 2 '15 at 4:00

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$.
• Oh ok, I hadn't thought of simply substituting into $a^kb^k\equiv 1$... Thanks for clearing it up! – MathQuestion Nov 2 '15 at 4:27