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?
Answer
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}$$
No comments:
Post a Comment