# Simple Property of GCD and Modular Arithmetic

I'm stuck on proving a rather elementary property, as I'm not really sure how to start off the approach. Suppose $g^a\equiv 1$ mod $m$ and $g^b\equiv 1$ mod $m$. Does this imply that $g^{\gcd(a,b)}\equiv 1$ mod $m$?

Here's my attempt: By definition, we know that $m\mid g^a-1$ and $m|g^b-1$, so there exists some $x,y\in\mathbb{Z}$ such that $mx=g^a-1$ and $my=g^b-1$. Then \begin{align} m(x+y)&=g^{\gcd(a,b)}g^{\frac{a}{\gcd(a,b)}}+g^{\gcd(a,b)}g^{\frac{b}{\gcd(a,b)}}-2\\ &=g^{\gcd(a,b)}\Big(g^{\frac{a}{\gcd(a,b)}}+g^{\frac{b}{\gcd(a,b)}}\Big)-2. \end{align} However, I feel like this approach is only making the problem more complicated than it actually is, as the terms become harder and harder to manipulate to get our desired result $mz=g^{\gcd(a,b)}-1$ for some $z\in\mathbb{Z}.$

Any help would be appreciated!

• By Bezout's, there exists $u,v$ such that $au+bv=\gcd(a,b)$. Thus mod $m$: $g^{\gcd(a,b)}\equiv g^{au+bv}\equiv\cdots$
– anon
Commented Jun 21, 2012 at 6:48
• Thanks. As described, I just wasn't sure which of the many properties to try out, but this one proves it quite easily. Commented Jun 21, 2012 at 7:14
• When you have several things to try, you should actually try them rather than become paralyzed with indecision. You really shouldn't be stuck on a problem until you're at the point where you can't think of anything reasonable to try.
– user14972
Commented Jun 21, 2012 at 9:01
• Also, if it's choosing among many options that's giving you trouble, then you should say so! Without prompting, very few people will even think about offering advice on that topic. In this case, I suspect the answer most people would give is "there was one or more obvious things to try, so I tried them and it was quickly clear that <method of choice> would work". Of course, what's obvious to them might not have been obvious to you -- so such advice may not be helpful if you don't share what alternatives you saw and what you thought about them.
– user14972
Commented Jun 21, 2012 at 9:06
• Sure, I understand, but this comes at the cost of being long-winded, making it harder for others to contribute to the problem at hand without having understood (or at least glimpsed through) the majority of what I would have written down. I feel the current content was accurate enough to explain my overally situation without becoming verbose. Commented Jun 21, 2012 at 9:35

We have by the extended Euclidean algorithm that there exists $x, y \in \Bbb{Z}$ such that $ax + by = gcd(a,b)$. So $$g^{gcd(a,b)} = g^{ax+by} = g^{ax} \cdot g^{by} = (g^a)^x \cdot (g^b)^y \equiv 1^x\cdot 1^y = 1 \pmod{m}.$$
• Ah, thank you. There's many different properties on $\gcd$ and I wasn't necessarily sure which one would provide the simplest proof. This makes perfect sense though, since we can easily split them in the manner you wrote out. Commented Jun 21, 2012 at 7:13
We do not even need Bézout's Theorem. All we need is to know that the original Euclidean Algorithm (with subtraction) terminates with the $\gcd$. Let $a\gt b$, and let $c=a-b$. Note that $\gcd(b,c)=\gcd(a,b)$.
We have $g^{c}g^{b}=g^{a}$, and therefore if $g^a\equiv 1\pmod{m}$ and $g^b\equiv 1 \pmod{m}$ then $g^c\equiv \pmod{m}$.
It is easy: $\rm\ \ g^A,\,g^B\equiv 1\:\Rightarrow\,order(g)\, |\, A,B\:\Rightarrow\: order(g)\, |\, (A,B)\:\Rightarrow\: g^{\,(A,B)}\equiv 1\quad$ QED