Thread: GCD question View Single Post

## GCD question

Ok im trying to solve this question.

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

This is what i got:

$$x = 0$$ then $$gcd(0, n) = gcd(n-0, n) = n$$

$$x = n/2$$ then $$gcd(n/2, n) = gcd(n-n/2, n) = n/2$$

$$0 < x < n/2$$ then $$x = n/k$$ for some $$k>2$$

$$gcd(n/k, kn/k) = n/k$$ because $$n = kn/k$$

so $$n - n/k = kn/k - n/k = (kn - n)/k = (k-1)n/k$$

therefore $$gcd(n-x, n) = gcd((k-1)n/k, kn/k) = n/k$$

therefore $$gcd(x, n) = gcd(n-x, n)$$

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 $$\phi(n)$$ is an even number. Where $$\phi(n)$$ is the eurler function.

Im having trouble with this one. Can anyone help me out?
 PhysOrg.com science news on PhysOrg.com >> City-life changes blackbird personalities, study shows>> Origins of 'The Hoff' crab revealed (w/ Video)>> Older males make better fathers: Mature male beetles work harder, care less about female infidelity