Dowód, że 641 dzieli 2³² + 1

Rozwiń komentarz aby poznać gotowiec

Najpierw zauważmy, że:

641 = 640 + 1

640 = 5 * 2⁷

641 = 5 × 2⁷ + 1, a więc 5 × 2⁷ ≡ -1 (mod 641) // brakuje jedynki przy dzieleniu przez 641, więc -1 mod 641

Można zapisać 2⁷ ≡ -5⁻¹ (mod 641)

Podnosimy do jak największej potęgi aby jak najbardziej zbliżyć się do 2³², ale nie przeskoczyć.

(2⁷)⁴ ≡ (-5⁻¹)⁴ = 5⁻⁴ (mod 641),

A więc 2²⁸ ≡ 5⁻⁴ (mod 641).

Zauważamy, że 2³² = 2²⁸ × 16, a więc mnożymy obie strony przez 16

2²⁸ × 16 ≡ 16 × 5⁻⁴ (mod 641).

Teraz 5⁴ = 625. 625 jest mniejsze niż 641, brakuje 16. Interesuje nas sama reszta z dzielenia

5⁴ = 625 = 641 - 16 ≡ -16 (mod 641).

Skracamy: 16 × 5⁻⁴ ≡ 16 × (-16)⁻¹ = 16 × (-1 × 16⁻¹) = -1 (mod 641).

Wynika, z tego, że 2³² ≡ -1 (mod 641), brakuje jeden przy dzieleniu przez 641, żeby podzielić całkowicie

A więc 2³² + 1 ≡ 0 (mod 641) Jest podzielne przez 641

1. Każda liczba jest podzielna przez każdą ( ͡° ͜ʖ ͡°) trzeba było zaznaczyć, że ma być bez powtórzeń hehuhuehueh

Dane:

x = 641 = 64*10+1 = 2^5 x10 +1 = 2^5 x 2*5 +1 = 2^6 x5 +1

y = 2^32+1

y/x=n (gdzie n jest liczbą naturalną).

Resztę podliczę jak wezmę do ręki zeszyt i długopis, daj mi chwilę.

Mmmmm... kongruencje :D

2 do potegi 8 to 256 256x256x256x256= 4 294 967 296 +1= 4 294 967 297/641= 6 700 417

Liczylem na kartce bez kalkulator

@entropy_ 2x32+1 =64+1=641 a to jestem niemal pewny, ze jest podzielne przez 641,