I was trying to find all integers $k$ that verify $\gcd(k+8,18)=1$ and I have no idea where to start. I tried thinking of Bezout but it doesn't lead me anywhere.
Asked
Active
Viewed 83 times
-1
-
2Hint: first show that, if $k$ works, then so does $k+18$. – lulu Mar 08 '20 at 12:12
-
Welcome to Mathematics Stack Exchange. Also, can you solve $\gcd(n,18)=1$? – J. W. Tanner Mar 08 '20 at 12:18
-
$18=2\times3^2$ – J. W. Tanner Mar 08 '20 at 12:37
1 Answers
2
Observe that $\gcd(n,18) = 1$ implies that $n$ is not divisible by $2,3$ since $18 = 2\cdot 3^2$. Since any integer can be written as $n = 6p+r, 0\le r \le 5$. Since $n$ is not divisible by either $2$ or $3$, $n = 6p+1$ or $n = 6p+5$. Apply this argument for $n = k+8$, we have: $k+8 =6p+1$ or $k+8 = 6p+5$. So $k = 6p-7$ or $k = 6p-3$. Thus $ k= 6p'+5$ or $k = 6p'+3$. Here $p' = p-2$. In summary: $k = 6m+5$ or $k = 6m+3$ where $m \in \mathbb{Z}$.
DeepSea
- 77,651
-
thank you so much ! but may I ask was there a certain reason as to why you chose studying cases in Z/6Z and not for example in Z/9Z ? – OUCHNA Mar 08 '20 at 15:02
-
-
@OUCHNA Beware: the "implies that" should say "if and only if" else to be correct we'd need to explicitly verify that the all the claimed solutions work (i.e. are not extraneous). – Bill Dubuque Mar 08 '20 at 18:47