Matematik

Talteoretisk Bevis

21. maj 2007 af stræber-pigen (Slettet)

a^(phi n) ==1 mod n

Bevis:

phi n repræsenterer de primiske restklasser mod n som er

a1,a2, ... , a(phi n)

Hvordan kommer jeg videre?

Brugbart svar (0)

Svar #1
21. maj 2007 af sheaf (Slettet)

Hint:

Indse at der gælder kongruensen:

(a*a1)(a*a2)*...*(a*a_phi(n)) == a1*a2*...*a_phi(n) (mod n)

og argumenter for, at der kan deles med a1*a2*...*a_phi(n), hvorefter resultatet foreligger.

Svar #2
21. maj 2007 af stræber-pigen (Slettet)

Ja, men det er lige dét jeg ik kan se?

Svar #3
21. maj 2007 af stræber-pigen (Slettet)

Derefter bruger man nemlig forkortningssætningen..
Men hvordan kan man se at

(a*a1)(a*a2)*...*(a*a_phi(n)) == a1*a2*...*a_phi(n) (mod n)
?

Brugbart svar (0)

Svar #4
21. maj 2007 af peter lind

* er kommutativ, så du kan flytte om på rækkefølgen som det passer dig. Her skal du vælge rækkefølgen, så alle a'er kommer sidst.

Brugbart svar (0)

Svar #5
21. maj 2007 af sheaf (Slettet)

De phi(n) tal a_1,...,a_phi(n) er alle positive heltal mindre end n som er indbyrdes primiske med n. Da nu sfd(a,n)=1 må ethvert af tallene a*a_1,a*a_2,...,a*a_phi(n) være konkruent modulo n med eet af tallene a_1,a_2,...,a_phi(n). Produktet af disse kongruenser netop som angivet i #1.

Af kommentaren i #4 følger nu at det er ækvivalent med

a^phi(n)*(a1*a2*...*a_phi(n)) == a_1*a_2...*a_phi(n) (mod n)

Overvej nu, om ikke sfd(a_1*a_2*...*a_phi(n),n)=1 således at omtalte division kan foretages.

Brugbart svar (0)

Svar #6
21. maj 2007 af peter lind

Jeg er senere kommet til at tænke på om du mente noget andet med dit spørgsmål, nemlig bevis for at

(a*a1)*(a*a2)* ... (a*aphi(n)) = a1*a2* ... aphi(n)

Det skyldes at hvis a*ai = a*aj så er ai = aj, hvilket kan ses ved at gange på begge sider med den inverse til a.

Det betyder at alle a*ai så må være forskellige, og da antallet af elementer a*ai er den samme som antallet af invertible elementer, må hver element forekomme netop en gang. Mængden {a1, a2, ...
aphi(n)} må derfor være den samme som mængden {(a*a1), (a*a2) ... (a*aphi(n)). I de fleste tilfælde vil rækkefølgen være en anden.

Indsætter du dette får du

(a*a1)*(a*a2)* ... (a*aphi(n)) = a1*a2* ... aphi(n) = a1*a2* ... aphi(n)*a^phi(n) og heraf

a^phi(n) mod 1 = 1

Skriv et svar til: Talteoretisk Bevis

Du skal være logget ind, for at skrive et svar til dette spørgsmål. Klik her for at logge ind.
Har du ikke en bruger på Studieportalen.dk? Klik her for at oprette en bruger.