Competition problem — Number theory

Library / /135 of 520

Number theory Difficulty 5.7 AIME, harder Find the answer

8. If $n$ is a natural number less than 50, find all values of $n$ such that the values of the algebraic expressions $4 n+5$ and $7 n+6$ have a common divisor greater than 1.

Let the above text be translated into English, please retain the original text's line breaks and format, and output the translation result directly.

Your answer

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

8. Solution: Let $(4 n+5,7 n+6)=d>1$ , then $d|(4 n+5), d|(7 n+6)$
Thus $d \mid(7 n+6-(4 n+5))=3 n+1$ ,
$\begin{array}{l} d \mid((4 n+5)-(3 n+1))=n+4 \\ d \mid((3 n+1)-2(n+4))=n-7 \\ d \mid((n+4)-(n-7))=11 \end{array}$

Since 11 is a prime number, then $d=11$ .
Let $n-7=11 k$ , then
$0<n=11 k+7<50$ . Solving for $k$ gives $k=0,1,2,3$ .
Thus $n=7,18,29,40$ .

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.