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?
|