8 svar
231 visningar
Ampere 188
Postad: 26 jan 2022 20:11

Bevisa kongruens

Hej!

Jag ska bevisa att ap bp (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

rp ≡ rp (mod n)

Men är verkligen detta ett bevis? 

Metod 2: 

a-b = qn   → a = qn + b 

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

 

Tack på förhand!

DrMuld 111
Postad: 26 jan 2022 22:10

Hur kommer du fram till att

(kn+r)prp (mod 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.

Ampere 188
Postad: 27 jan 2022 18:03

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å?

Smutsmunnen 1048
Postad: 27 jan 2022 19:57

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

Om du har ett utryck som (kn+r)pkan du utveckla det tex med binomialsatsen?

Ampere 188
Postad: 27 jan 2022 21:15

Binomialsatsen har vi inte gått igenom ännu. 

Vad är det andra sättet?

Smutsmunnen 1048
Postad: 27 jan 2022 21:46

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

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

Ampere 188
Postad: 28 jan 2022 20:24

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.

Smutsmunnen 1048
Postad: 29 jan 2022 13:18

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?

Ampere 188
Postad: 30 jan 2022 19:19

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
Close