Største felles divisor

[Lord X]

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...

[=)]

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

[Lord X]

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

Tror ikke jeg forstår hva du skriver her. Hva betyr f.eks. a_1a_2...a_n?

[=)]

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.

[Lord X]

Ok, da så. Men hvordan kan en gjøre det uten å blande inn primtallsfaktorisering? (dvs. bare reglene for delelighet, gcd etc.)

[=)]

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.

[fbhdif]

1)
Gitt gcd(a,b)=1, vis at då må gcd(ac,b)=gcd(c,b)

Siden a og b ikke har noen felles faktorer, vil følgelig de eneste faktorene ac og c har til felles være de felles faktorene til c og b.

[Lord X]

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.

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...

[fbhdif]

hverken a eller b behøver å være primtall for at gcd(a,b) = 1.

hva med for eksempel gcd(10, 33).

[kalleja]

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

[Lord X]

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)