Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
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. –  Dustin Tran 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. –  Dustin Tran Jun 21 '12 at 9:35

3 Answers 3

up vote 3 down vote accepted

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

share|improve this answer
    
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. –  Dustin Tran 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}$.

share|improve this answer

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

share|improve this answer
    
See this post for more. For an application see here. –  Bill Dubuque Jun 26 '12 at 0:50

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.