Liczba złożona

[pow3r]

Wykaż, że jeśli \(\displaystyle{ n>0}\) jest liczbą złożoną, to \(\displaystyle{ (10^n-1)/9}\) też jest złożona.
Wykaż, że twierdzenie odwrotne nie jest prawdziwe.

[Premislav]

Niech \(\displaystyle{ n=pq}\) dla całkowitych dodatnich \(\displaystyle{ p,q}\) większych niż \(\displaystyle{ 1}\), wówczas
\(\displaystyle{ 10^n-1=(10^p)^q-1^q=(10^p-1) \sum_{k=0}^{q-1}10^{pk}}\)

Wynika to z ogólniejszego wzoru: \(\displaystyle{ a^m-b^m=(a-b) \sum_{k=0}^{m-1} a^{m-1-k}b^k}\) dla \(\displaystyle{ m\in \NN^+}\), tutaj \(\displaystyle{ a=10^p, \ b=1}\).
Czyli
\(\displaystyle{ \frac{10^n-1}{9} = \frac{10^p-1}{9} \cdot \sum_{k=0}^{q-1}10^{pk}}\)
i oba czynniki są całkowite (zauważ, że \(\displaystyle{ 10^p\equiv 1\pmod{9}}\)) oraz większe od \(\displaystyle{ 1}\) (bo \(\displaystyle{ p, q>1}\)).

Z drugiej strony \(\displaystyle{ \frac{10^3-1}{9} =111=3\cdot 37}\) jest złożona, a wszakże liczba \(\displaystyle{ 3}\) nie jest złożona.

[bakala12]

Przedstawię inne rozwiązanie.
Zauważmy, że ta liczba składa się z samych jedynek!
Stąd łatwo widać, że jeżeli \(\displaystyle{ k|n}\) to \(\displaystyle{ \underbrace{11\dots 1}_{k}|\underbrace{11 \dots 1}_{n}}\), co dowodzi naszej tezy.

Dowód tego co łatwo widać:    

Niech \(\displaystyle{ n=dk}\). Wówczas \(\displaystyle{ \underbrace{11\dots 1}_{n} = \underbrace{11\dots 1}_{k}\left(10^{\left(k-1\right)d} + 10^{\left(k-2\right)d}+\dots + 1\right)}\)

Kontrprzykład na niepoprawność pokazał Premislav, tutaj nie mam wiele więcej do powiedzenia.

Jeszcze jedno. Prawdziwe jest takie twierdzenie (kontrapozycja Twojego zadania):

Jeżeli liczba \(\displaystyle{ \underbrace{11 \dots 1}_{n}}\) jest pierwsza, to \(\displaystyle{ n}\) jest też pierwsza.

Ciekawostką niech będzie fakt, że najmniejszym \(\displaystyle{ n>2}\) dla którego liczba \(\displaystyle{ \underbrace{11 \dots 1}_{n}}\) jest pierwsza jest \(\displaystyle{ n=23}\).