Indukcja Witcher77: Wykazać, że dla każdej liczby naturalnej n i każdej liczby nieparzystej k liczba k²ⁿ−1 jest podzielna przez 2ⁿ⁺²

wredulus_pospolitus: na początek wykażemy, że dla dowolnego 'k' nieparzystego mamy taką podzielność dla n = 1) 1) k = 1 1²¹ − 1 = 1¹ − 1 = 0 = 2¹⁺²*0 2) k = j j²¹ − 1 = 2³m 3) k = j+2 (j+2)²¹ − 1 = (j+2)² − 1 = j² − 1 + 4j + 4 = // (z 2) // = 2³m + 4(j+1) = 2³m + 4*2l (bo j+1 to liczba parzysta) b) teraz udowodnimy, że jeżeli dla określonego k zachodzi ta podzielność dla jakiegoś n, to zachodzi także dla (n+1) 1) n = 1 k²ⁿ − 1 = 2ⁿ⁺²*m <−−− to de facto wykazaliśmy powyżej −−− cały ten dowód był to wykazywał 2) n = s k^2s −1 = 2^s+2*m 3) n = s+1 k^2s+1 − 1 = k^2s*2 − 1 = (k^2s)² − 1 = (k^2s − 1)(k^2s + 1) = // z (2) // = = 2^s+2m*( 2^s+2*m + 2) = 2^s+2m*2*( 2^{s+2 − 1}m + 1) = 2^(s+1)+2m*( 2^{s+2 − 1}m + 1) c.n.w.

wredulus_pospolitus: na spokojnie przeanalizuj czy wiesz dlaczego to wyczerpuje wszystkie możliwości i dowodzi prawdziwości dla dowolnego (nieparzystego) k i dowolnego (naturalnego) n ewentualnie jeszcze dowód dla n=0 trzeba przeprowadzić (zamiast n=1) −−− to zależy jak zdefiniowany jest zbiór liczb naturalnych

Witcher77: Czy mógłbyś/mogłabyś wytłumaczyć jeszcze co się stało w ostatniej linijce po zastąpieniu nawiasów założeniem z (2) ? Od tego=2ⁿ⁺²*m*2*(.... Skąd to się wzięło ?

Adamm: to jest prawdziwe dla n>0, dla n = 0 nie

wredulus_pospolitus: przed podstawieniem założenia: (k^2s − 1)*(k^2s + 1) = (k^2s − 1)*(k^2s − 1 + 2) <−−− może z tej postaci łatwiej będzie Ci zauważyć za co podstawiałem

Adamm: Dla n=1, 8|k²−1 = (k−1)(k+1) bo k−1, k+1 są parzyste, a (k−1)/2, (k+1)/2 to dwie kolejne liczby naturalne. Załóżmy, że 2ⁿ⁺²|k²ⁿ−1 dla każdego nieparzystego k, n>0. Wtedy k²ⁿ⁺¹−1 = (k²ⁿ−1)(k²ⁿ+1). 2|k²ⁿ+1 oraz 2ⁿ⁺²|k²ⁿ−1, więc 2ⁿ⁺³|k²ⁿ⁺¹−1. Zatem na mocy indukcji, 2ⁿ⁺²|(k²ⁿ−1) dla każdego n>0 i nieparzystych k.

Adamm: Tak poza tym, przypomina mi to o tkzw. tocjencie Carmichaela. λ(2ⁿ⁺²) = φ(2ⁿ⁺²)/2 = 2ⁿ, n>0. Tzn. k²ⁿ ≡ 1 (mod 2ⁿ⁺²) dla k względnie pierwszych z 2ⁿ⁺² (czyli nieparzystych)

Witcher77: Dziękuję