# 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!

-

5
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 Jun 21 '12 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. – Riem Jun 21 '12 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. – Hurkyl Jun 21 '12 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. – Hurkyl Jun 21 '12 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. – Riem Jun 21 '12 at 9:35

## 3 Answers

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. – Riem Jun 21 '12 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

-

See this post for more. For an application see here. – Gone Jun 26 '12 at 0:50
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 29, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9684948921203613, "perplexity_flag": "head"}