1
$\begingroup$

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

How to do these type of questions?

$\endgroup$
6
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

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