0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ I don't know if this works but suppose a prime $p \neq 3$ divides both $n$ and $3(n - 1).$ $p \mid 3(n - 1) \implies p \mid (n - 1).$ Hence, $p$ is a common factor for both $n$ and $n - 1.$ But $n$ and $n - 1$ are always coprime. Hence, it follows that for $n$ multiple of 3, this holds. $\endgroup$ – green frog Mar 20 '17 at 8:09
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.