Bevisa kongruens

Hej!

Jag ska bevisa att a^p $\equiv$ b^p (mod n), om jag vet om att a ≡ b (mod n). Jag har tänkt ut två metoder, men jag undrar om de är rätt.

Metod 1:

Jag har börjat med att anta att a = kn +r och att b = zn+r

Därefter har jag skrivit om det första uttrycket så att det blir:

(kn +r)^p ≡ (zn +r)^p (mod n)

Nu kan jag konstatera att det går att skriva om som

r^p ≡ r^p (mod n)

Men är verkligen detta ett bevis?

Metod 2:

a-b = qn → a = qn + b

Då blir det: (qn+b)^p ≡ b^p (mod n) Och här kommer det bli b^p^≡b^p (mod n)

Tack på förhand!

Hur kommer du fram till att

${(k n + r)}^{p} \equiv r^{p} (m o d n)$ ?

Om du kan motivera detta så håller Metod1 (de kanske finns en formel som säger detta? annars är det inte så svårt att se att det måste vara så)

Du behöver samma sak i Metod2.

Jag tänkte att kn alltid kommer att vara delbart med n, till skillnad från resten r.

T.ex. så är ju 15 ≡ 5 (mod 10) och 15 är ju detsamma som (10+5).

Är dock fortfarande själv tveksam till om jag får göra den omskrivningen.

Finns det något annat sätt som man kan bevisa det på?

Ja det finns minst två sätt att göra detta på.

Om du har ett utryck som ${(k n + r)}^{p}$ kan du utveckla det tex med binomialsatsen?

Binomialsatsen har vi inte gått igenom ännu.

Vad är det andra sättet?

Ok det finns minst tre sätt att göra detta på.

Om ni inte gått igenom binomialsatsen så kanske induktion? Över p.

Problemet är att jag fortfarande inte har lärt mig om bevismetoder ännu.

Alltså ska man enligt läroboken bevisa det enbart med hjälp av kunskaper om kongruens.

Ok om ni varken gått igenom induktion eller binomialsatsen tänker jag ungefär så här.

Om man börjar med specialfallet p=2? Hur skulle du bevisa det?

Då p=2 gäller väl att resten för a upphöjs i 2? Och det borde väl vara detsamma som för b, dvs resten för b upphöjs också till 2?

Ännu en fråga, var min metod 1 och metod 2 korrekta efter min motivering?

Svara

Visa senaste svar