Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?
I want the old design back!!! :-)

Problem B. 4228. (December 2009)

B. 4228. The sequence pn is defined recursively: Let p1=2 and let pn+1 be the largest prime factor of p_1p_2\ldots p_n+1. Is 11 a term of the sequence?

(5 pont)

Deadline expired on January 11, 2010.


Sorry, the solution is available only in Hungarian. Google translation

Megoldás. A sorozat minden eleme prímszám. Nyilván \(\displaystyle p_2=3\), \(\displaystyle p_3=7\), és a sorozatban minden prímszám legfeljebb egyszer szerepel, hiszen a sorozat minden eleme relatív prím az azt megelőző elemekhez. Tegyük fel, hogy a sorozatban szerepel a 11, ekkor valamely \(\displaystyle n\ge 3\) esetén a \(\displaystyle p_1p_2\ldots p_n+1\) szám prímosztói között csak az 5 és a 11 szerepelhet, hiszen a többi 11-nél kisebb prímhez biztosan relatív prím. Ez a szám tehát \(\displaystyle 5^a\cdot11^b\) alakba írható alkalmas \(\displaystyle a,b\) nemnegatív egész számokkal. Erre a számra teljesül, hogy

\(\displaystyle 5^a\cdot11^b-1=p_1p_2\ldots p_n\)

osztható 2-vel, 3-mal és 7-tel is, de nem osztható 4-gyel. Mivel \(\displaystyle 5^a\) néggyel osztva 1 maradékot ad, \(\displaystyle 11^b\) nem adhat 1 maradékot, hiszen akkor \(\displaystyle 5^a\cdot11^b\) is 1 maradékot adna. Ezért \(\displaystyle b\) csak páratlan szám lehet. Ekkor \(\displaystyle 11^b\) hárommal osztva 2 maradékot ad. Ahhoz, hogy \(\displaystyle 5^a\cdot11^b\) hárommal osztva 1 maradékot adjon, az szükséges, hogy \(\displaystyle 5^a\) hárommal osztva 2 maradékot adjon, ami csak úgy lehet, ha \(\displaystyle a\) is páratlan. Ekkor viszont alkalmas \(\displaystyle u\) egész számmal \(\displaystyle 5^a\cdot11^b=55u^2\). Mivel 55 héttel osztva 6 maradékot ad, a négyzetszámok pedig 0, 1, 2, vagy 4 maradékot adnak, könnyen ellenőrizhető, hogy \(\displaystyle 55u^2-1\) nem lehet osztható 7-tel. Ezért a sorozatban nem szerepelhet a 11.


Statistics:

38 students sent a solution.
5 points:Ágoston Péter, Ágoston Tamás, Boér Lehel, Cséke Balázs, Damásdi Gábor, Dudás 002 Zsolt, Éles András, Énekes Péter, Gyarmati Máté, Hajnal Péter János, Janzer Olivér, Karl Erik Holter, Kiss 902 Melinda Flóra, Márkus Bence, Máthé László, Mester Márton, Mészáros András, Nagy Balázs, Németh Bence, Neukirchner Elisabeth, Perjési Gábor, Popper Dávid, Somogyi Ákos, Szabó 928 Attila, Weisz Ágoston, Weisz Gellért, Zsakó András.
4 points:Nagy Róbert.
3 points:5 students.
2 points:2 students.
0 point:3 students.

Problems in Mathematics of KöMaL, December 2009