+0  
 
0
45
1
avatar

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

 Aug 14, 2023
 #1
avatar+121 
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

5 Online Users

avatar
avatar
avatar