# relating GCD, congruency and congruent classes

So some of you may have noticed my algebra exam is tomorrow!

The question is: If $[a]_{n} = [1]_{n}$ prove that $\mathrm{gcd}(a, n) = 1$.

Well I tried it one way. We know the above means the following: $a \equiv 1 \pmod{n}$. This is also written as $1 \equiv a \pmod{n}$ Then the gcd of these are as follows: $$\mathrm{gcd}(a, n) := d$$ and $$\mathrm{gcd}(1, n) := d'.$$

At this point I thought $d = d'$ which is NOT the case as pointed out by roommate. but lets assume it does so I finished the proof as follows:

$$\mathrm{gcd}(a,n) = \mathrm{gcd}(1, n)$$ $$\mathrm{gcd}(a, n) = 1$$

but then obviously that's not the case (or is it). I then tried the following: $$d = as + nt, \quad s, t \in \mathbb{Z}$$ $$d' = as' + nt', \quad s', t' \in \mathbb{Z}.$$

And now I'm stuck again :(

-

Yes, the GCDs are the same, but your argument shows a lot of confusion, as Bill points out. First, when you claim that $d=d'$, the problem is that you are simply asserting a result that is stronger than what you are trying to prove. You are trying to prove the simpler case that if $a\equiv 1 \pmod{n}$ then $\gcd(a,n)=1$, and you are invoking the result that if $a\equiv b\pmod{n}$ then $\gcd(a,n)=\gcd(b,n)$. That's more than what you want to prove, so you cannot simply assume it's true.

But really, think about $[a]_n = [1]_n$. That means that $1 = a+kn$ for some integer $k$. That means that you can write $1$ as a linear combination of $a$ and $n$. That means that $\gcd(a,n)$ divides $1$. That means...

-
We actually tried that, but we dont know what to do after? I tried the linear combination way but how do we end the proof using that? –  Tyler Hilton Nov 16 '10 at 16:21
@Tyler Hinton: So, you know that the gcd divides $1$. You should also know that the gcd is positive. How many positive integers do you know that divide $1$? –  Arturo Magidin Nov 16 '10 at 16:53
ohhhhh i only know of one positive integer that divides one. which is 1. awesome. didn't even think that way! so does that complete my proof? –  Tyler Hilton Nov 16 '10 at 19:37
@Tyler Hilton: Well, that completes my proof; if you write it up properly, then it will also be your proof. (-; –  Arturo Magidin Nov 16 '10 at 19:38

HINT $\rm\ \ d\:|\:n,\:1+kn\ \Rightarrow\ d\:|\: 1$

-
hey thanks, but we were right the first time. The GCD of those two are the same. –  Tyler Hilton Nov 15 '10 at 23:57
What you wrote above shows confusion about basic points. I recommend that you write out your purported proof here so that we can help you further. –  Bill Dubuque Nov 16 '10 at 0:03