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
An interesting glimpse into how future state-of-the-art electronics might work
Tissue regeneration using anti-inflammatory nanomolecules
C2D2 fighting corrosion