# Find the least $n$ such that the fraction is reducible

So I have this type of question I've never seen before. It smells like Number Theory to me, and I've never studied Number Theory, but I know a very few, very basic Number Theory facts. For instance I know Fermat's Little Theorem, that for any two integers their GCD is some linear combination of the numbers, and I have some basic facility with manipulating and reasoning with integer modules (Or are the called "residues"? I've heard both words, not super clear on the difference.).

Anyway, the problem is to find the least positive $n$ such that $\dfrac{n-13}{5n+6}$ is a positive reducible fraction. I can see that this means finding the least $n$ such that $\gcd(n-13, 5n+6)>1$ but I don't know what to do with that. I've been trying to think about it as: the numerator "starts" at 1 (for $n=14$ to get a positive numerator) and the denominator starts at 76. From there the numerator increments by 1 and the denominator increments by 5, as $n$ increments by 1. Again, though, since I want to stop searching when I've found any factor, I'm not sure what to do with this either.

I know I can get an upper bound on the number by choosing $n$ a factor of both 13 and 6 which would have $\operatorname{lcm}(6,13) = 78$. But checking manually to find a number between 14 and 78 to see if there's anything lower seems like it's not the kind of thing we should be doing. But I don't see any guarantee that there wouldn't be some other solution in that interval.

Any thoughts or suggestions please?

• Try carrying out the Euclidean algorithm on $gcd(n-13, 5n+6)$ and see what you get. You need this to be greater than 1... – Johanna Oct 30 '14 at 23:00
• @Johanna Step 1 of the Euclidean algorithm, find a quotient and remainder. $5n+6 = q(n-13) + r$ where this equation seems completely unsolvable for $q$ and $r$ given that I don't know $n$. If $q$ is 5 I get $r$ a number vastly larger than $q$ so I can say $q\ne 5$. For any other value $(5-q)n + 6-13q = r$ but I feel like I'm spinning my tires. – Addem Oct 30 '14 at 23:08

## 2 Answers

Euclidean division is the key. Since $$5n+6 = 5(n-13) + 71$$ We see that $\text{gcd}(5n+6, n-13)$ must divide 71, which is prime. As you say, we want $\text{gcd}(5n+6, n-13)$ to be greater than $1$, so it must be $71$. In particular $$n-13 = 71k \quad \Longrightarrow \quad n = 13+71k$$ The least value is $n=84$ for $k=1$, and therefore $$\frac{n-13}{5n+6} = \frac{84-13}{5\cdot 84 + 6} =\frac{71}{426}$$ which is reducible because $$\frac{71}{426} = \frac{1}{6}$$

Hint: The first step in the Euclidean algorithm is $gcd(n-13,5n+6)=gcd(n-13, 5n+6-5(n-13))$

• I'll take your word for it, I've never seen that--I thought the first step of the Euclidean algorithm was to find $q$ and $0\leq r < q$ such that blah blah blah. In fact I'm not really sure what justifies the choice of the factor 5. But OK, assuming this is true, $gcd(n-13, 71)>1$ occurs for smallest $n$ when $n-13=72$ since 71 is prime, and so $n=85$. But when I plug in, the fraction is irreducible. I got no idea what's goin on. – Addem Oct 30 '14 at 23:17
• Now we have $gcd (n-13,71) \gt 1$, so we want $n=84$ Plugging that in gives $71/426$, which is reducible. – Ross Millikan Oct 30 '14 at 23:54