Kongruensrekning

Her kan du stille spørsmål vedrørende problemer og oppgaver i matematikk på høyskolenivå. Alle som har kunnskapen er velkommen med et svar. Men, ikke forvent at admin i matematikk.net er spesielt aktive her.

Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa

Svar
Mattebruker
Weierstrass
Weierstrass
Innlegg: 458
Registrert: 26/02-2021 21:28

La
n = 20200020x

vere eit 9-siffra naturleg tal (10-talsystemet ) . Bruk kongruensrekning til å bestemme det siste sifferet ( x ) slik at 17 I n
NB! Ingen digitale hjelpemiddel tillatne.
jos
Galois
Galois
Innlegg: 561
Registrert: 04/06-2019 12:01

Dette var hva jeg fikk til etter en gjenoppdagelse av et lite hefte om tallteori ute på nettet.


$n = 20200020x = {200 * 1000 * 1000 + 2 * 1000 * 1000 + 200 + x}$

hvor x er et heltall mellom -1 og 10.

$200\equiv{20 *10}\equiv{3 *10}\equiv{13}\equiv{-4}(mod 17)$

$1000\equiv{5 * 200}\equiv{-20}\equiv{-3}(mod 17)$

$n = {200 * 1000 * 1000 + 2 * 1000 * 1000 + 200 + x}\equiv{-4 * -3 * -3 + 2 * -3 * -3 -4 + x}$

$\equiv{-36 + 18 -4 + x}\equiv{-22 + x}\equiv 0( mod 17) => x = 5$
Sist redigert av jos den 31/03-2023 13:57, redigert 1 gang totalt.
Mattebruker
Weierstrass
Weierstrass
Innlegg: 458
Registrert: 26/02-2021 21:28

Korrekt løysing ! Håpar dette problemet gav meirsmak.

Løyste problemet omlag på same måten: 20200020x = 2 [tex]\cdot[/tex] 10[tex]^{8}[/tex] + 2[tex]\cdot[/tex]10[tex]^{6}[/tex] + 2[tex]\cdot[/tex]10[tex]^{2}[/tex] + x

10 [tex]\equiv[/tex] - 7 [tex]\Rightarrow[/tex] 10[tex]^{2}[/tex] [tex]\equiv[/tex] 49 [tex]\equiv[/tex] - 2 ( mod 17 )

10[tex]^{2}[/tex] [tex]\equiv[/tex] - 2 [tex]\Rightarrow[/tex] 10[tex]^{6}[/tex] = (10[tex]^{2}[/tex])[tex]^{3}[/tex] [tex]\equiv[/tex] ( -2 )[tex]^{3}[/tex] = -8 [tex]\equiv[/tex] 9 ( mod 17 )

10[tex]^{8}[/tex] = (10[tex]^{2}[/tex] )[tex]^{4}[/tex] [tex]\equiv[/tex] ( -2 )[tex]^{4}[/tex] = 16 [tex]\equiv[/tex] - 1 ( mod 17 ) , o.s.v.......


For ei tid tilbake foreslo Aleks855 å starte ein " studiering " i talteori på dette forumet. Herverande innsendar støttar forslaget fullt ut. For oss som ikkje var
innom talteorien i studietida , er her mykje å lære.

Føyer til to oppgaver som burde trigge interessa for denne greina av matematikken.

1) Løyse dette problemet utan å bruke kalkulator eller andre digitale hjelpemiddel:

Bestem resten ( naturleg tal ) når 52[tex]^{3}[/tex][tex]\cdot[/tex] 26 delast på 42.

2) Vis at talet 39 går opp i ( 53[tex]^{103}[/tex] + 103[tex]^{53}[/tex] )

La hjernetrim og påskekrim gå hand i hand. God fornøyelse og god påske !
jos
Galois
Galois
Innlegg: 561
Registrert: 04/06-2019 12:01

Takk for påsketrimmen!

Jeg prøver meg på oppgave 2.

Det skal vises at $\,53^{103} + 103^{53} \equiv 0 (mod\, 39)$

Tar i bruk Eulers utvidelse av Fermats lille teorem.

Antallet ikke nullelementer mindre enn $39$ som er innbyrdes primiske med $39 $

er $39 - (3 + 12) = 24$

$\,53^{103} + 103^{53} = 53^{4 * 24} * 53^7 + 103^{2 * 24}103^5 \equiv 1^4 * 53^7 + 1^2 * 103^5\equiv 53^7 + 103^5\,(mod \,39)$

$53\equiv 14 \,(mod\, 39),\,14^2 = 196 \equiv 1\, (mod\,39),\, \,103 \equiv -14\,(mod\,39)$

$53^7 + 103^5\equiv 14^{2 * 3} * 14 + (-14)^4 * -14\equiv 1^3 *14 + 1^2 * (-14) = 14 - 14\equiv 0\,(mod\,39)$
Mattebruker
Weierstrass
Weierstrass
Innlegg: 458
Registrert: 26/02-2021 21:28

Takk for tilbakemelding ! Og nok ein gong: Korrekt svar !

Eulers teorem gir [tex]\varphi[/tex] ( 39 ) = [tex]\varphi[/tex] ( 3 [tex]\cdot[/tex] 13 ) = [tex]\varphi[/tex]( 3 ) [tex]\cdot[/tex] [tex]\varphi[/tex]( 13 ) = [ [tex]\varphi[/tex]( p ) = p - 1 ] = 2 [tex]\cdot[/tex] 12 = 24 ( OK ! )

Lurer på om Eulers teorem kjem til sin rett i denne oppgåva.
I staden for å gå vegen om Euler , kunne vi like gjerne ha gått " rett på sak ". Men dette er ei subjektiv vurdering frå mi side. I denne samanhengen kunne det vere greitt å få
innspel( kommentar ) frå nokon som har lang fartstid innan talteorien, jamfør Gustav & Co )

Mitt løysingsforslag:
( 1 ) 53[tex]\equiv[/tex] ( - 1 ) [tex]\Rightarrow[/tex] ( 53[tex]^{103}[/tex] ) [tex]\equiv[/tex] ( - 1 )[tex]^{103}[/tex] = - 1 ( mod 3 )
( 2 ) 103 [tex]\equiv[/tex] 1 [tex]\Rightarrow[/tex] ( 103[tex]^{53}[/tex] [tex]\equiv[/tex] 1[tex]^{53}[/tex] = 1 ( mod 3 )

( 1 ) og ( 2 ) medfører at ( 53[tex]^{103}[/tex] + 103[tex]^{53}[/tex] ) [tex]\equiv[/tex] 0 ( mod 3 )

Same reknemåte viser at ( 53[tex]^{103}[/tex] + 103[tex]^{53}[/tex] ) [tex]\equiv[/tex] 0 ( mod 13 )

Konklusjon : Uttrykk [tex]\equiv[/tex] 0 ( mod 3 ) [tex]\wedge[/tex] Uttrykk [tex]\equiv[/tex] 0 ( mod 13 ) [tex]\Rightarrow[/tex] Uttrkk [tex]\equiv[/tex] 0 ( mod 39 )
Gustav
Tyrann
Tyrann
Innlegg: 4555
Registrert: 12/12-2008 12:44

Mattebruker skrev: 02/04-2023 11:44
Mitt løysingsforslag:
( 1 ) 53[tex]\equiv[/tex] ( - 1 ) [tex]\Rightarrow[/tex] ( 53[tex]^{103}[/tex] ) [tex]\equiv[/tex] ( - 1 )[tex]^{103}[/tex] = - 1 ( mod 3 )
( 2 ) 103 [tex]\equiv[/tex] 1 [tex]\Rightarrow[/tex] ( 103[tex]^{53}[/tex] [tex]\equiv[/tex] 1[tex]^{53}[/tex] = 1 ( mod 3 )

( 1 ) og ( 2 ) medfører at ( 53[tex]^{103}[/tex] + 103[tex]^{53}[/tex] ) [tex]\equiv[/tex] 0 ( mod 3 )

Same reknemåte viser at ( 53[tex]^{103}[/tex] + 103[tex]^{53}[/tex] ) [tex]\equiv[/tex] 0 ( mod 13 )

Konklusjon : Uttrykk [tex]\equiv[/tex] 0 ( mod 3 ) [tex]\wedge[/tex] Uttrykk [tex]\equiv[/tex] 0 ( mod 13 ) [tex]\Rightarrow[/tex] Uttrkk [tex]\equiv[/tex] 0 ( mod 39 )
Ser riktig ut dette 8-)

La $k=53^{103} + 103^{53}$. Hvis $k\equiv 0\pmod{3}$ og $k\equiv 0\pmod{13}$ fins $n,m\in \mathbb{Z}$ slik at $k=3n=13m$. Fra Euclids lemma følger at $13|n$, så det fins et heltall $q$ slik at $n=13q$, ergo er $k=3\cdot 13\cdot q=39q$, og det betyr at $k\equiv 0\pmod{39}$.
jos
Galois
Galois
Innlegg: 561
Registrert: 04/06-2019 12:01

Jeg ser at Gustav bruker en emoj med sotfarget glass. Så det er mulig at han spøker med oss. Jeg har store problemer med å forstå hans bevisforslag. Påstanden som skal bevises, er at heltallet $ k = 53^{103} + 103^{53}$ er delelig med $39$. Jeg er enig i at hvis k er delelig med $39$, er k også delelig med $3$ og $13$ og at k dermed kan skrives som $3n$, $13m$ eller $3\cdot13\cdot q,\,$ hvor $n,m\, $og$\, q$ er heltall,
og hvor $k = 3n = 3\cdot13\cdot q\,$ følger av Euklids lemma. Men $k = 3\cdot13\cdot q\,$ hviler jo på betingelsen k er delelig med 39. Så det som bevises er at hvis k er delelig med 39, så er k delelig med 39.

Et bevis her må involvere uttrykket $ k = 53^{103} + 103^{53}$ og $39,\,$ikke bare at $39 = 3\cdot 13$.
Gustav
Tyrann
Tyrann
Innlegg: 4555
Registrert: 12/12-2008 12:44

Jeg spøker ikke. Mattebruker viser først at $k$ er delelig med både $3$ og $13$. Derfor fins heltall $n,m$ slik at $k=3n=13m$. Dermed vil primtallet $3$ dele $13m$. Euclid sier da at $3$ må dele minst et av tallene $13$ og $m$. Siden $3$ åpenbart ikke deler $13$, må derfor $3$ dele $m$. Dermed fins heltall $q$ slik at $m=3q$, og da vil $k=13m=13\cdot 3q=39q$. Så $k$ er delelig med $39$.

Bevis for den motsatte veien (uten behov for Euclid): Hvis $k$ er delelig med $39$ fins heltall $n$ slik at $k=39n=3p=13q$ der $p=13n, q=3n$. Ergo er $k$ delelig med både $3$ og $13$.
jos
Galois
Galois
Innlegg: 561
Registrert: 04/06-2019 12:01

Ser riktig ut dette 8-)

La $k=53^{103} + 103^{53}$. Hvis $k\equiv 0\pmod{3}$ og $k\equiv 0\pmod{13}$ fins $n,m\in \mathbb{Z}$ slik at $k=3n=13m$. Fra Euclids lemma følger at $13|n$, så det fins et heltall $q$ slik at $n=13q$, ergo er $k=3\cdot 13\cdot q=39q$, og det betyr at $k\equiv 0\pmod{39}$.
[/quote]

Det er mulig jeg har misforstått hva det ovenstående søker å bevise. Jeg tolket det som det søker å bevise at
$k=53^{103} + 103^{53}$ er delelig med $39$. Men så vidt jeg kan se er det som bevises, at hvis k er delelig med $3$ og også delelig med $13,$ så er k delelig med $3\cdot 13 = 39$. At $k=53^{103} + 103^{53}$ blir irrelevant i dette beviset.
En annen tolkningsmulighet, ser jeg nå, er at poenget med Gustavs innlegg ikke var å bevise at $k=53^{103} + 103^{53}$ er delelig med $39$, men å klargjøre en overgang i Mattebrukers bevis etter at Mattebruker først hadde vist at $k=53^{103} + 103^{53}$ er delelig med både $3$ og $13$.
Gustav
Tyrann
Tyrann
Innlegg: 4555
Registrert: 12/12-2008 12:44

jos skrev: 13/04-2023 14:31 En annen tolkningsmulighet, ser jeg nå, er at poenget med Gustavs innlegg ikke var å bevise at $k=53^{103} + 103^{53}$ er delelig med $39$, men å klargjøre en overgang i Mattebrukers bevis etter at Mattebruker først hadde vist at $k=53^{103} + 103^{53}$ er delelig med både $3$ og $13$.
Ja, dette er helt riktig tolket!
Mattebruker
Weierstrass
Weierstrass
Innlegg: 458
Registrert: 26/02-2021 21:28

Takk for innspel !
I mitt løysingforslag tok eg for gitt at k [tex]\equiv[/tex] 0 ( mod 3 ) og samtidig k [tex]\equiv[/tex] 0 ( mod 13 ) [tex]\Rightarrow[/tex] k [tex]\equiv[/tex] 0 ( mod 39 )
Om eg har forstått deg rett , er dette ein påstand( implikasjon ) som har krav på ei grunngjeving. Og det har du gjort, enkelt og greitt , ved å bruke eit verktøy ( lemma ) av
den greske oldtidsmatematikaren Euklid. Elegant !
Tilbake til mi løysing. Ser no i ettertid at vi kan relativt lett vise ovanståande påstand ( k [tex]\equiv[/tex] 0 ( mod 39 ) ) utan å dele opp divisor( 39 ) i primfaktorar.
53[tex]\equiv[/tex]14 ( mod 39 ) [tex]\Rightarrow[/tex] 53[tex]^{2}[/tex] [tex]\equiv[/tex] 14[tex]^{2}[/tex] = 196 [tex]\equiv[/tex] 1 ( mod 39 ) ...o.s.v.....
103[tex]\equiv[/tex] -14 [tex]\Rightarrow[/tex] 103[tex]^{2}[/tex] [tex]\equiv[/tex] ( - 14 )[tex]^{2}[/tex] = 196 [tex]\equiv[/tex] 1 ( mod 39 ) ........o.s.v......
Svar