If $n\in\Bbb N$, then gcd($8n+1, 7n+1)$ =

Question

How to do these type of questions?

score 6 · Answer 1 · answered Dec 08 '13 at 19:25

Suppose that $\gcd(8n+1,7n+1)=d$. Then $d\mid 8n+1$ and $d\mid 7n+1$, so $d\mid n=(8n+1)-(7n+1)$. Then we have $d\mid 1=(7n+1)-7n$. Therefore we must have $d=1$.

The general strategy is to take linear combinations of things you know are divisible by $d$.

score 4 · Answer 2 · answered Dec 08 '13 at 19:31

4

Pretty easy just using: $8(7n+1)-7(8n+1)=1$

answered Dec 08 '13 at 19:31

Thomas Andrews

177,126

score 0 · Answer 3 · answered Dec 08 '13 at 20:32

0

Or two steps of Euclid's algorithm. The first step yields n, the second step yields 1.

answered Dec 08 '13 at 20:32

Bill Kleinhans

1,458

If $n\in\Bbb N$, then gcd($8n+1, 7n+1)$ =

3 Answers3