Proving that gcd(x, n) = gcd(n-x, n) for 0 ≤ x ≤ n/2

[gimpy]

Ok I am 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?

 

[master_coda]

Originally posted by gimpy
$$0 < x < n/2$$ then $$x = n/k$$ for some $$k>2$$

This is not true, not if x, n and k are integers. For example, if n is prime then clearly this only works for x = 1.

This makes the proof easy, since making this (wrong) assumption is the same as assuming $\gcd(x,n)=x$.

 

[matt grime]

you're just working in the integers; always avoid writing fractions, so you don't make impossible calculations.


here, it is a trivial exercise with the following definition of gcd:

let I(a,b) be the ideal in Z of all numbers of the form ax+by, for x,y integers.

the gcd is the minimal positive element of this ideal. here it is trivial because clearly I(a,b) and I(a-b,b) are the same set.

if you've another definition for gcd use it, perhaps by linking this to your defintion.

 

[gimpy]

Yeah ok, i guess i am just working with integers, if i wasn't then gcd wouldn't make sense right? But why does it say that $$0 \leq x \leq n/2$$, can't x be any real number? And when you subtract $$n-x$$ wouldn't this be any real number and not an integer depending on what value x is? Or is it that i am only supposed to choose an x such that $$n-x$$ is an integer?

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

Originally posted by matt grime
you're just working in the integers; always avoid writing fractions, so you don't make impossible calculations.


here, it is a trivial exercise with the following definition of gcd:

let I(a,b) be the ideal in Z of all numbers of the form ax+by, for x,y integers.

the gcd is the minimal positive element of this ideal. here it is trivial because clearly I(a,b) and I(a-b,b) are the same set.

if you've another definition for gcd use it, perhaps by linking this to your defintion.

 

[master_coda]

An inequality such as $0\leq x\leq n/2$ doesn't always mean x is a real number. You have to consider the context. And in this case the numbers you're working with (x and n) must be integers, since the idea of divisiblity doesn't have any meaning when talking about real numbers.

 

[matt grime]

Originally posted by gimpy
Yeah ok, i guess i am just working with integers, if i wasn't then gcd wouldn't make sense right? But why does it say that $$0 \leq x \leq n/2$$, can't x be any real number? And when you subtract $$n-x$$ wouldn't this be any real number and not an integer depending on what value x is? Or is it that i am only supposed to choose an x such that $$n-x$$ is an integer?

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

You are working in the ring of integers. Why should you be able to pass to the ring of Real numbers?
I don't know why that inequality is placed in the question.

Here's a simple direct proof as you didn't say the indirect one was useful.


suppose r divides n and n-x, then r divides n-(n-x)=x. ie it divides n and x.


suppose now that r divides n and x, well, then it trivially divides n-x.

So the set of divisors of n and x, and the set of divisors of n-x and n are the same. And the maximal element in the set must be the same to (they are finite sets). Absolutely no need to invoke any inequality. I'd ask why your teacher out it there, or let us know which book this is taken from.


As the the Euler totient function. first show that

phi(ab)=phi(a)phi(b) if a and b are coprime, then deduce it suffices to workout phi(q) for q some power of a prime p. This is easy to do by hand by counting multiples of p less than q