Matematik
Problem GCD
08. september 2007 af
math-freak++ (Slettet)
Lad n tilhøre N og a,b tilhøre Z.
Antag a==b mod n.
Vis gcd(a,n)=gcd(b,n).
ax+ny=bx+ny, men så er a=b ?
Antag a==b mod n.
Vis gcd(a,n)=gcd(b,n).
ax+ny=bx+ny, men så er a=b ?
Svar #1
08. september 2007 af peter lind
Brug samme metode som bevis for euclids algoritme.
a=b+kn
største fælles devisor for b og n går op i højre side og må derfor gå op i både a og n. Derfor er største fælles devisor for b og n højst lig med den største fælles fælles devisor for a og n. Brug derefter samme metode til at vise at den modsatte ulighed også holder.
a=b+kn
største fælles devisor for b og n går op i højre side og må derfor gå op i både a og n. Derfor er største fælles devisor for b og n højst lig med den største fælles fælles devisor for a og n. Brug derefter samme metode til at vise at den modsatte ulighed også holder.
Svar #2
08. september 2007 af math-freak++ (Slettet)
#1 a = k*n + b. Så er gcd(b,n) går op i a, gcd(a,n) går op i b.
a > b, gcd(a,n) >= gcd(b,n). Hvordan kommer jeg videre?
a > b, gcd(a,n) >= gcd(b,n). Hvordan kommer jeg videre?
Skriv et svar til: Problem GCD
Du skal være logget ind, for at skrive et svar til dette spørgsmål. Klik her for at logge ind.
Har du ikke en bruger på Studieportalen.dk?
Klik her for at oprette en bruger.