Litt usikker på noen oppgaver her:
Oppgave 1
Gitt gcd(a,b)=1, vis at då må gcd(ac,b)=gcd(c,b)
Oppgave 2
Gitt gcd(a,b)=1 og c|(a+b), vis at gcd(a,c)=gcd(b,c)=1
Oppgave 3
Gitt gcd(a,b)=1, d|ac og d|bc, vis at d|c.
Oppgave 4
Hvis gcd(a,b)=1, vis at gcd(a^2,b^2)=1
Tror jeg har fått til noen av dem, men har ikke fasit så er ikke sikker...
Største felles divisor
Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
Tror ikke jeg forstår hva du skriver her. Hva betyr f.eks. a_1a_2...a_n?=) skrev:la a = a_1a_2...a_n
og b = b_1b_2...b_n
osv
i de forskjellige oppgavene og husk at
a_n [symbol:ikke_lik] b_m
uansett når gcd = 1
"There are three kinds of lies: lies, damned lies, and statistics"
Det jeg mener er at et naturlig tall a, består av et endelig (edit:) antall primtalls faktorer, som du konsekvent kan skrive som [tex]a_1 \cdot a_2 \cdot a_3 \cdot ... \cdot a_n[/tex] det samme kan du gjøre med et naturlig tall b, bare husk hvis [tex]gcd(a,b)=1[/tex] så deler de ingen primtallsfaktorer.
Sist redigert av =) den 20/11-2007 20:01, redigert 1 gang totalt.
vel siden gcd(a,b) er produktet av alle primtallsfaktorene a og b deler så har jeg mine tvil at man kan unngå primtall her.
edit: litt misledende, det er produktet av alle primtallsfaktorene a og b deler, hvis ikke de deler noen så er gcd(a,b)=1.
edit: litt misledende, det er produktet av alle primtallsfaktorene a og b deler, hvis ikke de deler noen så er gcd(a,b)=1.
Oppgavene står iallefall i et kapittel som kommer før det som omhandler primtall, så jeg antar meningen er at jeg skal bruke det som står i det relevante kapitlet til å løse oppgavene...=) skrev:vel siden gcd(a,b) er produktet av alle primtallsfaktorene a og b deler så har jeg mine tvil at man kan unngå primtall her.
edit: litt misledende, det er produktet av alle primtallsfaktorene a og b deler, hvis ikke de deler noen så er gcd(a,b)=1.
"There are three kinds of lies: lies, damned lies, and statistics"
Oppgave 3
Gitt gcd(a,b)=1, d|ac og d|bc, vis at d|c.
Svar: er litt rusten her, men tror jeg klarer dette. siden gcd(a,b)=1 så har a og b ingen like primtallsfaktorer. Når da d|ac så vil d være en faktor som er lik med en faktor i a, c eller begge. Siden også d|bc vil d være en faktor i b, c eller begge. Men her kan vi fort luke bort at a og b har begge like primtallsfaktorer som d, siden d ikke kan deles både a og b samtidig( jmf. gcd(a,b)=1). Og ergo må d|c.
Noter også at d kan dele a eller b samtidig som c, men ikke begge, slik at d er en primtallsfaktor i a og c eller b og c. Eks: gcd(10,33)=1 og 3|10*6 og 3|33*6, Men også at 3|33. . .
Oppgave 4
Hvis gcd(a,b)=1, vis at gcd(a^2,b^2)=1
Svar: Hvis vi primtallsfaktoriserer a og b får vi to unike primtallsfaktoriseringer. og siden ingen av faktorene i a er lik faktorene i b, vil det heller ikke bli slik når vi kvaderer a og b. det vil bare gi oss en mer av hver primtallsfaktor som vi allerede har i a og b. ergo vil a^2 og b^2 ikke ha noen like faktorer, (samme sak med a^24 og b^354 for den slags skyld.) slik at gcd(a^2,b^2)=1
Gitt gcd(a,b)=1, d|ac og d|bc, vis at d|c.
Svar: er litt rusten her, men tror jeg klarer dette. siden gcd(a,b)=1 så har a og b ingen like primtallsfaktorer. Når da d|ac så vil d være en faktor som er lik med en faktor i a, c eller begge. Siden også d|bc vil d være en faktor i b, c eller begge. Men her kan vi fort luke bort at a og b har begge like primtallsfaktorer som d, siden d ikke kan deles både a og b samtidig( jmf. gcd(a,b)=1). Og ergo må d|c.
Noter også at d kan dele a eller b samtidig som c, men ikke begge, slik at d er en primtallsfaktor i a og c eller b og c. Eks: gcd(10,33)=1 og 3|10*6 og 3|33*6, Men også at 3|33. . .
Oppgave 4
Hvis gcd(a,b)=1, vis at gcd(a^2,b^2)=1
Svar: Hvis vi primtallsfaktoriserer a og b får vi to unike primtallsfaktoriseringer. og siden ingen av faktorene i a er lik faktorene i b, vil det heller ikke bli slik når vi kvaderer a og b. det vil bare gi oss en mer av hver primtallsfaktor som vi allerede har i a og b. ergo vil a^2 og b^2 ikke ha noen like faktorer, (samme sak med a^24 og b^354 for den slags skyld.) slik at gcd(a^2,b^2)=1
Ok, skal se om jeg forstår det (men som sagt tror jeg det var meningen jeg skulle gjøre oppgavene på en måte som ikke blander inn primtallsfaktorisering; har ikke hatt kapitlet om primtall som pensum).
Forresten, har et par oppgaver til som jeg tror jeg har fått til, men er ikke sikker på om resonnementene mine er gyldige. Kan noen bekrefte eller avkrefte? De omhandler både gcd og kongruensregning:
Vis at når i) ab [symbol:identisk] cd (mod n) og ii) b [symbol:identisk] d (mod n) samt gcd(b,n)=1 så er:
a [symbol:identisk] c (mod n)
Svar:
i) og ii) impliserer at n går opp i både ab-cd og b-d. Da vil n også gå opp i en lineær kombinasjon av disse: n|(ab-cd)x + (b-d)y for heltall x og y.
Setter x=1 og y=-c og får at: n|ab-bc eller n|b(a-c)
Siden gcd(n,b)=1, har vi ifølge Euklids lemma at n|(a-c), noe som igjen impliserer at a [symbol:identisk] c (mod n)
Gitt i) a [symbol:identisk] b (mod n1) og ii) a [symbol:identisk] c (mod n2), vis at b [symbol:identisk] c (mod d) der d=gcd(n1,n2):
Svar:
i) og ii) betyr at a-b og a-c er multiplum av hhv. n1 og n2, f.eks:
a-b=kn1 og a-c=qn2
Da blir: b=a-kn1 og c=a-qn2 og b-c vil følgelig bli (a-kn1)-(a-qn2)=qn2-kn1.
Ser på så d=gcd(n1,n2). Siden d går opp i både n1 og n2, vil også d gå opp i en lineær kombinasjon av disse: d|(n1)x+(n2)y.
Setter vi x=-k og y=q får vi at: d|b-c
eller, ekvivalent, at b [symbol:identisk] c (mod d)
Forresten, har et par oppgaver til som jeg tror jeg har fått til, men er ikke sikker på om resonnementene mine er gyldige. Kan noen bekrefte eller avkrefte? De omhandler både gcd og kongruensregning:
Vis at når i) ab [symbol:identisk] cd (mod n) og ii) b [symbol:identisk] d (mod n) samt gcd(b,n)=1 så er:
a [symbol:identisk] c (mod n)
Svar:
i) og ii) impliserer at n går opp i både ab-cd og b-d. Da vil n også gå opp i en lineær kombinasjon av disse: n|(ab-cd)x + (b-d)y for heltall x og y.
Setter x=1 og y=-c og får at: n|ab-bc eller n|b(a-c)
Siden gcd(n,b)=1, har vi ifølge Euklids lemma at n|(a-c), noe som igjen impliserer at a [symbol:identisk] c (mod n)
Gitt i) a [symbol:identisk] b (mod n1) og ii) a [symbol:identisk] c (mod n2), vis at b [symbol:identisk] c (mod d) der d=gcd(n1,n2):
Svar:
i) og ii) betyr at a-b og a-c er multiplum av hhv. n1 og n2, f.eks:
a-b=kn1 og a-c=qn2
Da blir: b=a-kn1 og c=a-qn2 og b-c vil følgelig bli (a-kn1)-(a-qn2)=qn2-kn1.
Ser på så d=gcd(n1,n2). Siden d går opp i både n1 og n2, vil også d gå opp i en lineær kombinasjon av disse: d|(n1)x+(n2)y.
Setter vi x=-k og y=q får vi at: d|b-c
eller, ekvivalent, at b [symbol:identisk] c (mod d)
"There are three kinds of lies: lies, damned lies, and statistics"