1
$\begingroup$

I am trying to show that $7n + 4$ and $5n + 3$ are coprime for all $n \in \mathbb Z$ but I'm stuck.

Please could someone tell me how to show this?

What I tried:

My first attempt was to use that two numbers are coprime iff their $\gcd$ is $1$. So assume that there are integers $k,q$ such that $1 = 7kn + 4k + 5qn + 3q$.

And this is where my first attempt ended as I did not see a way to proceed from there.

My second attempt was to use that if $b> a$ then $\gcd(a,b) = \gcd(b, b-a)$ so

$$ \gcd (7n + 4, 5n + 3) = \gcd (5n + 3, 2n + 1)$$

but this idea also seems to lead nowhere as I don't see how to show that $\gcd (5n + 3, 2n + 1)=1$.

$\endgroup$
2
  • 6
    $\begingroup$ You only started. Repeat the dose! $$(5n+3)-(2n+1)=3n+2,\ldots$$ Soon this may turn into full blown Euclid's algorithm :-) $\endgroup$ Aug 23, 2015 at 6:47
  • $\begingroup$ As Jyrki said. Also, \gcd gets the upright version. $\endgroup$
    – user21820
    Aug 23, 2015 at 6:52

4 Answers 4

7
$\begingroup$

A quick way is to eliminate $n$, noting that $7(5n+3)-5(7n+4)=1$.

$\endgroup$
3
$\begingroup$

Using the fact that if $b>a$, then $\gcd(a,b) = \gcd(b, b-a)$, we have:

$\gcd (7n + 4, 5n + 3) = \gcd (5n + 3, 2n + 1)=\gcd (2n+1, 3n+2) = \gcd (3n+2, n+1)=\gcd (n+1, 2n+1) = \gcd (2n+1, n)= \gcd(n,n+1) = \gcd(n+1,1)$

$\endgroup$
1
$\begingroup$

Let $d$ be the $\gcd$. Then, $d|(5n+3-2n-1)=(3n+2), d|(3n+2-2n-1)=(n+1),d|(2n+1-2(n+1))=-1$ and so $d=1$.

$\endgroup$
0
$\begingroup$

You can find $a,b$ such that: $a(7n+4) + b(5n+3) = 1\to 7a+5b=0, 4a+3b=1\to -21a-15b=0, 20a+15b=5\to a = -5, b = 7$. This means $\gcd(7n+4,5n+3) = 1$.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged .