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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 :(

share|cite|improve this question
up vote 1 down vote accepted

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

share|cite|improve this answer
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$

share|cite|improve this answer
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

Your Answer


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.