Problem B. 4228. (December 2009)

B. 4228. The sequence p_n is defined recursively: Let p₁=2 and let p_n+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

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.

Already signed up?
New to KöMaL?