Thread: GCD question View Single Post
 P: 29 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?