Eulers generalisering för fermat's theorem.

Jag försöker mig förstå beviset som bilden visar.

If gcd(a,n) = 1, then a^φ(n) ≡ 1 (mod n).

Det jag inte förstår är vad representerar $y_{i}$ i detta kontext? Varför tar vi fram $y_{i}$ ?

Hej!

Det står i beviset att $y_i = ax_i + k_in$ där $k_i$ är ett heltal (notera att detta är en likhet); detta är innebörden i kongruensen $y_i \equiv ax_1\, (\text{ mod }n)$ .

Uttryckt i klartext: Heltalet $y_i$ är resten som du får då du delar heltalet $ax_i$ med heltalet $n$ .

Notera att det råder likhet

$\prod x_i = \prod y_i$

men att det råder kongruens modulo $n$

$\prod y_i \equiv a^{m}\cdot \prod x_i.$

Detta medför att det råder kongruens modulo $n$

$(a^m-1) \cdot \prod x_i \equiv 0$

vilket betyder att

antingen är $\prod x_i$ delbart med $n$ eller
så är $a^m-1$ delbart med $n.$

Du vet att $\prod x_i$ inte är delbart med $n$ eftersom inget av heltalen $x_i$ är delbart med $n.$ Därför måste det vara så att $a^m-1$ är delbart med $n$ , vilket är vad som skulle visas.

Svara