Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

GCD question

  1. Jan 31, 2004 #1
    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?
  2. jcsd
  3. Jan 31, 2004 #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 [itex]\gcd(x,n)=x[/itex].
    Last edited: Jan 31, 2004
  4. Jan 31, 2004 #3

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    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.
  5. Jan 31, 2004 #4
    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 [tex]0 \leq x \leq n/2[/tex], can't x be any real number? And when you subtract [tex]n-x[/tex] 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 [tex]n-x[/tex] is an integer?

    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].

  6. Jan 31, 2004 #5
    An inequality such as [itex]0\leq x\leq n/2[/itex] 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.
  7. Feb 2, 2004 #6

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    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
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook