Proof of $g^a \equiv 1 \pmod{m}$ and $g^b \equiv 1 \pmod{m} \quad \implies \quad g^{\gcd(a,b)} \equiv 1 \pmod{m}$

Question

I am trying to understand the following: $$g^a \equiv 1 \pmod m \quad \text{and} \quad g^b \equiv 1 \pmod{m} \quad \implies \quad g^{\gcd(a,b)} \equiv 1 \pmod{m}.$$

I have tried a few approaches, but I can't seem to find one that works out.

Answer 1

By Bézout's identity, there exists a pair of integers $(p,q)$ such that $p a+q b=\gcd(a,b)$.

We then get the following:

$g^{\gcd(a,b)}=g^{pa+qb}=(g^a)^p\cdot (g^b)^q \equiv 1^p \cdot 1^q\equiv 1 \pmod{m}$

EDIT: There is also the following straight forward argument if you don't know of Bézout's theorem:

Write $\gcd(a,b)=d$ so that $a=d \alpha$, $b=d\beta$, and $\alpha \perp \beta$.

Let $x$ be the order of the element $g^d=s$ in the group, then we get $s^x\equiv s^{\alpha} \equiv s^{\beta} \pmod{m}$.

Let $\alpha \equiv r_1 \pmod{x}$, $\beta \equiv r_2 \pmod{x}$ where $0\leq r_1,r_2<x$. Then $r_1$ and $r_2$ must both be equal to $0$, because if not, we get $s^{\alpha} \equiv s^{r_1}\equiv 1 \pmod{m}$, which contradicts the fact that $x$ is the order of $s$ (same argument for $r_2$).

Since $x$ divides the two coprime numbers $\alpha$ and $\beta$, $x$ must be equal to $1$, and so: $g^d=s^1\equiv 1 \pmod{m}$.

Answer 2

Hint:

Let $c$ be the smallest positive integer so that $g^c\equiv 1 \pmod m$.

You can prove that if $g^d \equiv 1 \pmod m$ then $c|d$.

Use integer division of $d$ by $c$: $d = qc+r$ with $0 \leq r < c$. Since $g^d \equiv g^c \equiv 1 \pmod m$ then $g^{d-qc} \equiv 1 \Rightarrow g^r \equiv 1$ but $c$ was the smallest positive number so that $g^c \equiv 1$, therefore $r = 0$.

That would mean that $c|a$ and $c|b$, so $c|\gcd(a,b)$, and therefore $g^{\gcd(a,b)} \equiv g^{ck} \equiv 1^k \equiv 1\pmod m$