Podzielność, liczby złożone

[Archaniol]

1. Udowodnić, że \(\displaystyle{ NWD(a^m-1,a^n-1)=a^{NWD(m,n)}-1}\), gdzie \(\displaystyle{ a \in N_+}\)

2.Niech \(\displaystyle{ a \in 2N_+}\). Dowieść, że \(\displaystyle{ NWD(a^{2m}+1,a^{2n}+1)=1}\) dla \(\displaystyle{ m \neq n}\). Wykorzystać ten fakt do dowodu, że istnieje nieskończenie wiele liczb pierwszych.

3.Dowieść, że istnieją dowolnie długie ciągi kolejnych liczb naturalnych, które są złożone.

[Vax]

1) Na początku zauważmy, że dla \(\displaystyle{ (m,n) = 1}\) mamy \(\displaystyle{ d = (a^m-1 , a^n-1)=a-1}\), istotnie, z założenia \(\displaystyle{ a^m \equiv 1\pmod{d} \wedge a^n \equiv 1\pmod{d}}\), niech \(\displaystyle{ t=ord_da}\), mamy \(\displaystyle{ t\mid m \wedge t\mid n \Rightarrow t \mid (m,n)=1 \Rightarrow t=1 \Rightarrow a \equiv 1\pmod{d}}\), ale \(\displaystyle{ a-1 \mid a^m-1 \wedge a-1 \mid a^n-1}\), więc istotnie \(\displaystyle{ (a^m-1,a^n-1) = a-1}\), załóżmy więc, że \(\displaystyle{ d = (m,n)}\), podstawmy \(\displaystyle{ m=dm' , n=dn' , (m',n')=1}\) wówczas \(\displaystyle{ (a^m-1,a^n-1) = ((a^d)^{m'}-1 , (a^d)^{n'}-1 = a^d-1 = a^{(m,n)}-1}\) qed.

W 2 coś nie tak, wystarczy przyjąć \(\displaystyle{ m=3 \wedge n=5}\) i oba wyrażenia \(\displaystyle{ a^{2m}+1}\) oraz \(\displaystyle{ a^{2n}+1}\) dzielą się przez \(\displaystyle{ a^2+1}\)

3) Każda liczba \(\displaystyle{ n!+2 , n!+3 , ... , n!+n}\) jest złożona.

Poprawiony bug w 1

[timon92]

1) Rozpatrzmy dowolną liczbę pierwszą \(\displaystyle{ p}\) taką, że \(\displaystyle{ p \mid a^m-1 \wedge p \mid a^n-1}\), czyli \(\displaystyle{ \begin{cases} a^m \equiv 1\pmod{p} \\ a^n \equiv 1\pmod{p}\end{cases}}\), niech \(\displaystyle{ t=ord_pa}\), czyli \(\displaystyle{ t\mid m \wedge t\mid n \Rightarrow t \mid (m,n) \Rightarrow a^{(m,n)} \equiv 1\pmod{p}}\), w drugą stronę jest oczywiste, że dla dowolnej liczby pierwszej \(\displaystyle{ p}\) mamy \(\displaystyle{ a^{(m,n)} \equiv 1\pmod{p} \Rightarrow a^m \equiv 1\pmod{p} \wedge a^n \equiv 1\pmod{p}}\), czyli \(\displaystyle{ p \mid a^m-1 \wedge p \mid a^n-1 \iff \ p \mid a^{(m,n)}-1}\), p było wybrane dowolnie, więc istotnie \(\displaystyle{ (a^m-1,a^n-1)=a^{(m,n)}-1}\)

jakby co to to rozwiązanie jest niepoprawne

natomiast w zadaniu 2 zapewne chodziło o liczby \(\displaystyle{ a^{2^m}+1, a^{2^n}+1}\)

pozdro