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.
Podzielność, liczby złożone
- Vax
- Użytkownik
- Posty: 2913
- Rejestracja: 27 kwie 2010, o 22:07
- Płeć: Mężczyzna
- Lokalizacja: Biała Podlaska / Warszawa
- Podziękował: 4 razy
- Pomógł: 612 razy
Podzielność, liczby złożone
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
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
Ostatnio zmieniony 9 paź 2012, o 20:12 przez Vax, łącznie zmieniany 1 raz.
- timon92
- Użytkownik
- Posty: 1657
- Rejestracja: 6 paź 2008, o 16:47
- Płeć: Mężczyzna
- Lokalizacja: Katowice
- Podziękował: 7 razy
- Pomógł: 472 razy
Podzielność, liczby złożone
jakby co to to rozwiązanie jest niepoprawneVax pisze: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}\)
natomiast w zadaniu 2 zapewne chodziło o liczby \(\displaystyle{ a^{2^m}+1, a^{2^n}+1}\)
pozdro