Thread: GCD question
View Single Post
gimpy
gimpy is offline
#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
Cougars' diverse diet helped them survive the Pleistocene mass extinction
Cyber risks can cause disruption on scale of 2008 crisis, study says
Mantis shrimp stronger than airplanes