Unsimplifying a Fraction

We know that the fraction $\frac{N-23}{7N+6}$ will not be in lowest terms when the greatest common divisor (gcd) of $N-23$ and $7N+6$ is greater than 1. We note that $7N+6= 7(N-23)+167$ which implies that $\gcd(N-23,7N+6)\mid167$ However, 167 is prime so both the numerator and denominator must be divisible by 167 in order for the fraction to not be in simplest form. Also, because $N-23$ must be divisible by 167, $N$ must be congruent to 23 mod 167. So the smallest value of $N$ congruent to 23 mod 167 is 190(because $N$ cannot equal 23)

Solution 1: Denote $N-23$ by $M.$ Then $7N+6= 7(M+23)+6=7M+167.$ If some prime $p$ divides both $M$ and $7M+167,$ it must divide $167.$ Because $167$ is prime, $p$ must equal $167,$ which happens if and only if $M=N-23$ is a multiple of $167.$ Since $N$ is positive and different from $23,$ the smallest such $M$ is $167.$ This gives $N=167+23=190.$

Solution 2: We have that $\begin{aligned} \gcd(N-23, 7N+ 6) & = \gcd((N-23)+6(N-23), 7N+6) \\ & = \gcd(7N-161 - (7N+6), 7N+6) \\ & = \gcd(167, 7N+6) \\ \end{aligned}$

Since $167$ is prime, the greatest common divisor is either $167$ or $1$ . If it is $1$ then the fraction would be simplified, thus it must be $167$ .

So, the smallest possible value for the numerator is $167$ , hence $N=167+23=190$ is the smallest possible value for $N$ .

We check that the fraction is not reduced when $N = 190$ : $\frac {N-23}{7N+6} = \frac {167}{167 \times 8}$ .

from the problem we know gcd(N-23,7N+6)=gcd(7N+6,23×7+6)>1 as 23×7+6=167 is a prime. so (7N+6) mod 167=0,7N+6=167x, (167x-6) mod 7=0. as 167 mod 7=6. we get (6x-6)mod 7=0,and x=1 , N=23 is illegal. so min solution for x is 1+7=8. so min solution for N is (167×8-6)/7.