Ok im trying to solve this question.(adsbygoogle = window.adsbygoogle || []).push({});

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?

**Physics Forums - The Fusion of Science and Community**

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# GCD question

Loading...

Similar Threads for question | Date |
---|---|

I Astrodynamics Question: Derivation of Sp. Orbital Energy? | Apr 6, 2018 |

I Direct Products of Modules ...Another Question ... ... | Mar 31, 2018 |

I Correspondence Theorem for Groups ... Another Question ... | Mar 24, 2018 |

I Question about inverse operators differential operators | Feb 9, 2018 |

**Physics Forums - The Fusion of Science and Community**