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 :(
Answer
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...
No comments:
Post a Comment