Enumerate $n$ such that $GCD(n, 3(n-1)) = 3$.

Question

Is there a way to enumerate all $n$ such that $GCD(n, 3(n-1)) = 3$. I am able to see that $n$ must be of the form $3(3k+1)$ or $3(3k+2)$, but I cannot go much further.

Answer 1

Its simple $n$ must be divisible by 3. Or specifically $3|n \Rightarrow 3k=n$. Proof: $(n, 3(n-1))=3 \Rightarrow 3|n\land3|3*(n-1)$ . Now if $3|n$ then $3\nmid(n-1),\because (n,(n-1))=1$[this can be proofed by using the properties of divisibility].

So when $3|3(n-1)$, then $3\nmid n-1$ and $$\therefore n=3k,$$ where, $\enspace k\in\ \mathbb{Z}$.

Answer 2

This isn't really an elementary answer. I did it this way just to see if I could do it this way. The idea is that, if integers $u$ and $v$ can be found such that $ua + vb = 1$, then $\gcd(a,b) = 1$.

If $n = 3k$, then $\gcd(n, 3(n-1)) = \gcd(3k, 3(3k-1)) = 3\gcd(k, 3k-1) = 3$ since $\color{red}{(3k-1)} - 3\color{red}k = 1$ implies $\gcd(k, 3k-1) = 1$.

If $n = 3k+1$, then $\gcd(n, 3(n-1)) = \gcd(3k+1, 9k)=1$ since $k(\color{red}{9k}) - (3k-1)\color{red}{(3k+ 1)} = 1$

If $n = 3k+2$, then $\gcd(n, 3(n-1)) = \gcd(3k+2, 9k+3)=1$ since $(5 k +3)\color{red}{(9 k + 3)} - (15 k + 4)\color{red}{(3 k + 2)}= 1$.

OK. So here is the elementary proof.

Suppose that $n$ and $3(n-1)$ are not relatively prime to each other.

Then there exists a prime number, $p$, that is common divisor of $n$ and $3(n-1)$.

So $p \mid n$ and either $p=3$ or $p \mid (n-1)$.

If $p \mid (n-1)$ then $p \not \mid n$. Hence $p=3$

If $p=3$, then $3 \mid n$.

Answer 3

Euclid's algorithm gives you that the GCD is equal to $\mathrm{gcd}(n, n-3)$, which is (by Euclid again) $\mathrm{gcd}(3, n-3)$, which is (by a backwards step of Euclid) $\mathrm{gcd}(3, n)$.

Now if $p$ is prime, we have $\mathrm{gcd}(p, n) = p$ if $p \mid n$, and $1$ otherwise.