Zadanie nr 1066117

Dla jakich liczb całkowitych dodatnich liczby 5 p + p+ 1 i 11 p + p+ 1 są pierwsze.

Rozwiązanie

Zauważmy, że

5 5 4 3 4 3 2 2 p + p+ 1 = (p + p + p )− (p + p + p )+ p + p+ 1 = = (p2 + p + 1)(p 3 − p 2 + 1).

Podobnie

11 11 10 9 10 9 8 p + p + 1 = (p + p + p ) − (p + p + p )+ + (p8 + p7 + p6) − (p7 + p6 + p5) + p 5 + p + 1 = = (p 2 + p + 1 )(p 9 − p8 + p6 − p5)+ (p2 + p + 1)(p3 − p2 + 1) = 2 9 8 6 5 3 2 = (p + p + 1 )(p − p + p − p + p − p + 1).

Jak wpaść na te rozkłady? – moim zdaniem najprościej jest policzyć największy wspólny dzielnik liczb p5 + p+ 1 i p11 + p + 1 używając algorytmu Euklidesa. Jak się to zrobi to wyjdzie 2 p + p + 1 . A jak wiemy, że oba wielomiany dzielą się przez to napisanie rozkładów jest już automatyczne.