Udowodnić z MTF i funkcji Eulera Marcin: Udowodnić (nie korzystając z indukcji), że dla każdego ℕ∍n zachodzi: 2730/(n¹³−n)

Vax: Zauważ, że 2730 = 2*3*5*7*13, z twierdzenia Eulera otrzymujemy: n⁵⁷⁶ == 1 (mod 2730) ⇒ n⁵⁷⁷ == n (mod 2730) Mamy wykazać n¹³ == n (mod 2730) Czyli wystarczy wykazać, że: n⁵⁷⁷ == n¹³ (mod 2730) ⇔n¹³(n⁵⁶⁴−1) == 0 (mod 2*3*5*7*13) Teraz wykażemy, że dane wyrażenie dzieli się przez każdy z tych czynników pierwszych. Dane wyrażenie dzieli się przez 2, jeżeli n jest parzyste to n¹³ dzieli się przez 2, jeżeli nieparzyste to n⁵⁶⁴−1. Dzieli się przez 3, jeżeli 3|n to 3|n¹³, jeżeli n=3k+1 v n=3k+2 to 3|n⁵⁶⁴−1 (można sobie te przykłady rozpisywać z dwumianu newtona, wystarczy pokazać, że 3 | 1⁵⁶⁴−1 oraz 3 | 2⁵⁶⁴−1) Dzieli się przez 5, jeżeli 5|n to 5|n¹³, w pozostałych przypadkach (tutaj już rozpatrywanie wszystkich przypadków byłoby za długie) korzystamy z MTF: n⁵ == n (mod 5) ⇔ n⁴ == 1 (mod 5) ⇒ n⁵⁶⁴ −1 == 0 (mod 5) Dzieli się przez 7, jeżeli 7|n to 7|n¹³, w pozostałych przypadkach: n⁷ == n (mod 7) ⇔ n⁶ == 1 (mod 7) ⇔ n⁵⁶⁴ − 1 == 0 (mod 7) Dzieli się przez 13, jeżeli 13|n to 13|n¹³ w pozostałych przypadkach: n¹³ == n (mod 13) ⇔ n¹² == 1 (mod 13) ⇔ n⁵⁷⁶ − 1 == 0 (mod 13). Wykazaliśmy, że dane wyrażenie dzieli się przez wszystkie dzielniki 2730, tym samym zachodzi n⁵⁷⁷ == n¹³ (mod 2730) ⇔ n¹³ == n (mod 2730) qed. Pozdrawiam.