Thread: GCD question
View Single Post
gimpy
#1
Jan31-04, 02:14 PM
gimpy's Avatar
P: 29
Ok im trying to solve this question.

Assume [tex]n \geq 3[/tex], prove that [tex]gcd(x, n) = gcd(n-x, n)[/tex] for all [tex]0 \leq x \leq n/2[/tex].

This is what i got:

[tex]x = 0[/tex] then [tex]gcd(0, n) = gcd(n-0, n) = n[/tex]

[tex]x = n/2[/tex] then [tex]gcd(n/2, n) = gcd(n-n/2, n) = n/2[/tex]

[tex]0 < x < n/2[/tex] then [tex]x = n/k[/tex] for some [tex]k>2[/tex]

[tex]gcd(n/k, kn/k) = n/k[/tex] because [tex]n = kn/k[/tex]

so [tex]n - n/k = kn/k - n/k = (kn - n)/k = (k-1)n/k[/tex]

therefore [tex]gcd(n-x, n) = gcd((k-1)n/k, kn/k) = n/k[/tex]

therefore [tex]gcd(x, n) = gcd(n-x, n)[/tex]

Im not sure if that is correct but it makes sense to me. Anyways after this qeustion i have to answer this one:

Use the previous question to prove that [tex]\phi(n)[/tex] is an even number. Where [tex]\phi(n)[/tex] is the eurler function.

Im having trouble with this one. Can anyone help me out?
Phys.Org News Partner Science news on Phys.org
World's largest solar boat on Greek prehistoric mission
Google searches hold key to future market crashes
Mineral magic? Common mineral capable of making and breaking bonds