delelg med 5

[dahle-g@online.no]

Oppgåva C2.58 R1 SIGMA
La n, m ϵ N. Vis at dersom n og m ikkje er deleleg med 5, er m4 – n4 deleleg med 5.

Kan denne oppgåva løysast på denne måten?

Når vi har fem tal etter kvarandre må eitt vere deleleg med 5.
Når m og n ikkje er deleleg med 5 må dei ha rest 1, 2, 3, eller 4 når vi deler med 5.

Vi testar alle moglege kombinasjonar med rest.
m = 5p + 1 (rest).
n = 5q + 1 (rest).

Dersom p = 5p + 1 og q = 5q + 2 så er m4 – n4, delelig med 5.
Dersom p = 5p + 1 og q = 5q + 3 så er m4 – n4, delelig med 5.
Dersom p = 5p + 1 og q = 5q + 4 så er m4 – n4, delelig med 5.
Dersom p = 5p + 2 og q = 5q + 1 så er m4 – n4, delelig med 5.
Dersom p = 5p + 2 og q = 5q + 3 så er m4 – n4, delelig med 5.
Dersom p = 5p + 2 og q = 5q + 4 så er m4 – n4, delelig med 5.
Dersom p = 5p + 3 og q = 5q + 1 så er m4 – n4, delelig med 5.
Dersom p = 5p + 3 og q = 5q + 2 så er m4 – n4, delelig med 5.
Dersom p = 5p + 3 og q = 5q + 4 så er m4 – n4, delelig med 5.
Dersom p = 5p + 4 og q = 5q + 1 så er m4 – n4, delelig med 5.
Dersom p = 5p + 4 og q = 5q + 2 så er m4 – n4, delelig med 5.
Dersom p = 5p + 4 og q = 5q + 3 så er m4 – n4, delelig med 5.

Viser det med eitt eksempel, Brukar pascals trekant i utrekninga:

m4 – n4 = (5p + 1)4 – (5q + 2)4

1∙(5p + 1)4 + 4∙(5p + 1)3 + 6∙(5p + 1)2 + 4∙(p + 1) + 1∙14
- (1∙(5q + 2)4 + 4∙(5q + 2)3 + 6∙(5q + 2)2 + 4∙(q + 2) + 1∙24

= 1∙(5p4) + 4∙(5p3∙11) + 6∙(5p2∙12) + 4∙(5p ∙13) + 1∙(14)
- (1∙(5q4) + 4∙(5q3∙21) + 6∙(5q2∙22) + 4∙(5q∙23) + 1∙(24)

= 625p4 + 500p3 + 150p2 + 20p + 1 - (625q4 + 1000q3 + 600q2 + 20q + 16)
= (625p4 + 500p3 + 150p2 + 20p) - (625q4 + 1000q3 + 600q2 + 160q) – 16 + 1
= (625p4 + 500p3 + 150p2 + 20p) - (625q4 + 1000q3 + 600q2 + 160q + 15)

= 5∙(125p4 + 100p3 + 30p2 + 4p) - 5∙(125q4 + 200q3 + 120q2 + 32q + 3)

s = (125p4 + 100p3 + 30p2 + 4p)
t = (125q4 + 200q3 + 120q2 + 32q + 3)

m4 – n4 = 5s – 5t, delelig med 5.

Reknar ein ut dei andre kombinasjonane får ein same resultatet m4 – n4 = 5s – 5t, delelig med 5.

[Aleks855]

Har ikke sett gjennom Sigma R1, men er du gjort kjent med Fermats lille teorem?

https://en.wikipedia.org/wiki/Fermat%27s_little_theorem

Jeg tror metoden din ville ført frem, men jeg tror ikke boka er så sadistisk at den vil få deg til å gjennomgå alle de permutasjonene.

[stensrud]

Enklere:
\begin{align*}
m^4-n^4&=(m^2-n^2)(m^2+n^2)\\
&=(m-n)(m+n)(m^2+n^2)\\
&\equiv (m-n)(m+n)(m^2-4n^2)\\
&= (m-n)(m+n)(m-2n)(m+2n)\\
&\equiv (m-n)(m-2n)(m-3n)(m-4n) \pmod{5},
\end{align*}
og siden hverken $m$ eller $n$ er delelige med $5$ så må nøyaktig én av faktorene over være delelig med $5$.

[Aleks855]

Bare for å utdype på kommentaren om Fermats lille:

Korollaret sier at $a^{p-1} \equiv 1 \pmod p$ for primtall $p$. Siden 5 jo er primtall, så kan vi bare si at $m^4 - n^4 \equiv 1-1 \equiv 0 \pmod 5$.

(Kan noen eventuelt bekrefte?)

[Gustav]

Bare for å utdype på kommentaren om Fermats lille:

Korollaret sier at $a^{p-1} \equiv 1 \pmod p$ for primtall $p$. Siden 5 jo er primtall, så kan vi bare si at $m^4 - n^4 \equiv 1-1 \equiv 0 \pmod 5$.

(Kan noen eventuelt bekrefte?)

Selvsagt rett, så lenge $a\not\equiv 0\pmod p$ naturligvis.

[dahle-g@online.no]

Hei!
Takk for god tilbakemelding.
Nei, har ikkje hørt om Fermats lille teorem.

Stensrud kan ikkje følge faktoriseringa di og forstår ikkje resonnementet,
kan Du utdype resonnementet ditt.

[Gustav]

Hei!
Takk for god tilbakemelding.
Nei, har ikkje hørt om Fermats lille teorem.

Stensrud kan ikkje følge faktoriseringa di og forstår ikkje resonnementet,
kan Du utdype resonnementet ditt.

Det eneste han har brukt er konjugatsetningen gjentatte ganger, samt at 1 er ekvivalent med -4, og 2 ekvivalent med -3, som rester ved divisjon med 5.

[dahle-g@online.no]

Hei!
m^4 - n^4 = (m^2 - n^2)(m^2 - n^2)
= (m - n)(m + n)(m^2 + n^2)
= korleis har ein komt frå over til neste under frå (m^2 + n^2)
= (m - n)(m + n)(m^2 - 4n^2)
= (m - n)(m + n)(m - 2n)(m + 2n)
korleis har ein komt frå over til neste under
= (m - n)(m - 2n)(m - 3n)(m - 4n)

[Gustav]

Hei!
m^4 - n^4 = (m^2 - n^2)(m^2 - n^2)
= (m - n)(m + n)(m^2 + n^2)
= korleis har ein komt frå over til neste under frå (m^2 + n^2)
= (m - n)(m + n)(m^2 - 4n^2)
= (m - n)(m + n)(m - 2n)(m + 2n)
korleis har ein komt frå over til neste under
= (m - n)(m - 2n)(m - 3n)(m - 4n)

På det første spørsmålet, så er 1 og -4 ekvivalente som rester ved divisjon med 5. Grunnen er at differansen er 5, som er det samme som 0 som rester modulo 5. Derfor er $n^2$ og $-4n^2$ ekvivalente.

Søk opp modulær aritmetikk. En forklaring finnes også på side 21 i denne linken http://www.mn.uio.no/ibv/tjenester/kunn ... /talla.pdf

[dahle-g@online.no]

Takk for tipset, forstod det no utan å gå til henvisninga, men skal sette meg godt inni den også.
Forstår ikkje at dei kan lage slike oppgåver som er utan for det emnet kapittel 2 R1 lærebok Sigma.