Kezdőlap


Feladat:	F.3023	Korcsoport: 14-15	Nehézségi fok: átlagos
Megoldó(k):	Braun Gábor , Burcsi Péter , Farkas Péter , Fekete Zsolt , Gémes Tamás , Greguska Tamás , ifj. P. Tóth Béla , Lovász Zoltán , Póczos Barnabás , Rózsa Gábor , Véber Miklós
Füzet:	1995/január, 32 - 33. oldal		PDF \| MathML
Témakör(ök):	Legnagyobb közös osztó, Euklideszi algoritmus, Feladat
Hivatkozás(ok):	Feladatok: 1994/szeptember: F.3023

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

A tört mindig értelmes, mert a nevező pozitív. Pontosan akkor lehet egyszerűsíteni, ha $5 n + 13$ és $11 n + 20$ legnagyobb közös osztója, $(5 n + 13; 11 n + 20)$ nagyobb, mint $1$ .
Többször felhasználva az $(a; b) = (a; b + k a)$ azonosságot (ami az euklideszi algoritmus alaplépése),

\begin{matrix} \begin{matrix} (5 n + 13; 11 n + 20) & = (5 n + 13; 11 n + 20 - 2 (5 n + 13)) = (5 n + 13; n - 6) = \\ = (5 n + 13 - 5 (n - 6); n - 6) = (43; n - 6) . \end{matrix} \end{matrix}

Mivel a 43 prímszám, a legnagyobb közös osztó csak 1 vagy 43 lehet. Akkor 43, ha

n - 6

osztható 43-mal. A tört tehát a

43 k + 6

alakú

n

-ekre egyszerűsíthető. Mivel ennek 1 és 1994 közé kell esni,

\begin{matrix} \begin{matrix} 1 \leq 43 k + 6 = n \leq 1994 \\ - \frac{5}{43} \leq k \leq 46 + \frac{10}{43} . \end{matrix} \end{matrix}

Mivel

k

egész, ez azt jelenti, hogy

0 \leq k \leq 46

. Ilyen

k

47 darab van, tehát a tört 47 esetben egyszerűsíthető.

Braun Gábor (Budapest, Szent István Gimn., II. o.t.)