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

Guest 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\).

SpectraSynth Aug 14, 2023