Ok im trying to solve this question.
Assume [tex]n \geq 3[/tex], prove that [tex]gcd(x, n) = gcd(nx, 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(n0, n) = n[/tex]
[tex]x = n/2[/tex] then [tex]gcd(n/2, n) = gcd(nn/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 = (k1)n/k[/tex]
therefore [tex]gcd(nx, n) = gcd((k1)n/k, kn/k) = n/k[/tex]
therefore [tex]gcd(x, n) = gcd(nx, 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?
