Matematyka.pl

1. Wykaż, że jeśli liczba \(\displaystyle{ 2^n+1}\) jest liczbą pierwszą, to n jest naturalną potęgą liczby \(\displaystyle{ 2}\).
2. Udowodnij, że reszta z dzielenia przez \(\displaystyle{ 7}\) liczby \(\displaystyle{ 15^n}\) dla \(\displaystyle{ n\in\NN}\) jest równa \(\displaystyle{ 1}\)

Pozdrawiam i dziękuję za wszelkie odpowiedzi.
Maks

PS.: Daje punkty za DOBRE rozwiązania

to nie będzie tolerowane, na przyszłość poleci ostrzeżenie
Sylwek

1) Jeśli n nie jest potęgą 2, to jest postaci:
\(\displaystyle{ n = 2^{k}\cdot b}\)
gdzie b jest nieparzyste. Wstawmy:
\(\displaystyle{ \left(2^{2^k}\right)^{b} + 1 = \left(2^{2^{k}} + 1\right)\cdot (2^{2^{k} (b-1)} - 2^{2^{k} (b-2)}\ldots +1)}\)
Czyli ta liczba nie jest pierwsza. Możemy tak zrobić zawsze, gdy wykładnik ma w rozkładzie na czynniki pierwsze jakąś liczbę nieparzystą.
2)
\(\displaystyle{ 15^{n} = (14 + 1)^{n} = \sum_{k=0}^{n} 14^{k} 1^{n-k} = \sum_{k=1}^{n} 14^{k} + 1}\)
Suma jest podzielna przez 7 (bo każdy wyraz jest dodatnią potęgą 14), zatem reszta to 1.

2. \(\displaystyle{ 15 \equiv 1 \ (mod 7) \\ 15^n \equiv 1^n \equiv 1 \ (mod 7)}\)
c.k.d.

1. Udowodnimy implikację równoważną: jeśli n nie jest naturalną potęgą liczby 2, to \(\displaystyle{ 2^n+1}\) nie jest liczbą pierwszą (patrz: kwadrat logiczny). Zatem n możemy przedstawić w postaci: \(\displaystyle{ n=2^k r}\), gdzie r jest liczbą nieparzystą większą od jedynki. Zatem na mocy wzorów skróconego mnożenia:
\(\displaystyle{ 2^n+1=2^{2^k r}+1=(2^{2k})^r+1=(2^{2k}+1)((2^{2k})^{r-1}-(2^{2k})^{r-2}+\ldots+1)}\)