0

I'm currently stumped on this question:

Let $a$ and $m$ be integers such that $m\ge1$. Consider the congruence class of $a$, i.e., $[a]$ modulo $m$. Prove that: For all $x\in[a]$, $\gcd(x,m)=\gcd(a,m)$.

From this, I know that the congruence class of $[a]$ modulo $m$ is the set of integers
$[a]={x\in Z|x\equiv a\pmod m}$}. And by the Linear Congruence Theorem, $x\equiv a\pmod m$ if and only if $\gcd(x,m)|a$. I'm not sure where I can go from knowing this. Any ideas?

Przemysław Scherwentke
  • 13,668
  • 5
  • 35
  • 56
E 4 6
  • 243

2 Answers2

3

The congruence class of $a$ consists of all numbers of the form $a+qm$, where $q$ ranges over the integers. So we want to show that for all $q$, we have $\gcd(a,m)=\gcd(a+qm,m)$.

We can attack this directly. (i) Show that if $k$ divides $a$ and $m$, then $k$ divides $a+qm$ and $m$; (ii) Show that if $k$ divides $a+qm$ and $m$, then $k$ divides $a$ and $m$.

André Nicolas
  • 507,029
2

Another way to write your equivalence class: $x\equiv a \mod m \iff a=km+x$ for an integer $k$, which you can easily prove since $a\equiv b\mod m\iff m|(a-b)$.

Now I suggest thinking about the Euclidean algorithm, and you might find yourself being done fairly soon.

Edit: I've just looked at your criterion $x\equiv a\mod m\iff GCD(x,m)|a$ again, and it seems wrong to me. Take $x=1,m=3$, for instance. $GCD(3,1)=1|a$ for any integer $a$, but obviously $1\equiv a\mod 3 \quad\forall a\in\mathbb{Z}$ is not true.

Some Math Student
  • 1,502