+0

# GCD

0
7
1

Find the smallest positive integer $n$ such that $9n-2$ and $7n + 1$ share a common factor greater than $1$.

Aug 14, 2023

#1
0

We are looking for the smallest positive integer $$n$$ such that the two integers $$9n - 2$$ and $$7n + 1$$ share a common factor greater than $$1$$.

To find the common factors, we can compute the greatest common divisor (GCD) of these two numbers. Mathematically:

$\text{GCD}(9n - 2, 7n + 1).$

Let's use the Euclidean algorithm to calculate the GCD:

\begin{align*}
\text{GCD}(9n - 2, 7n + 1) &= \text{GCD}(9n - 2 - 7n - 1, 7n + 1) \\
&= \text{GCD}(2n - 3, 7n + 1).
\end{align*}

Continuing the process:

\begin{align*}
\text{GCD}(2n - 3, 7n + 1) &= \text{GCD}(2n - 3, 7n + 1 - 3 \cdot (2n - 3)) \\
&= \text{GCD}(2n - 3, n + 10).
\end{align*}

Now, for the two numbers to share a common factor greater than $$1$$, the GCD must be greater than $$1$$. We are looking for the smallest positive integer $$n$$ that satisfies this condition.

The GCD of $$2n - 3$$ and $$n + 10$$ will be greater than $$1$$ when $$n + 10$$ is not a multiple of $$2n - 3$$. In other words, $$2n - 3$$ must not divide evenly into $$n + 10$$.

We can try various values of $$n$$ to find the smallest $$n$$ for which this is true:

Let's start with $$n = 1$$:
$$2n - 3 = 2 - 3 = -1$$
$$n + 10 = 1 + 10 = 11$$

Since $$(-1)$$ does not divide evenly into $$11$$, this is a candidate.

Let's continue with $$n = 2$$:
$$2n - 3 = 4 - 3 = 1$$
$$n + 10 = 2 + 10 = 12$$

Since $$1$$ divides evenly into $$12$$, this is not a candidate.

So, the smallest positive integer $$n$$ that makes $$2n - 3$$ and $$n + 10$$ share a common factor greater than $$1$$ is $$n = 1$$.

Aug 14, 2023