Friday, June 8, 2018

elementary number theory - 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!


Answer



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


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...