grandes-ecoles 2014 QII.B.2

grandes-ecoles · France · centrale-maths2__mp Number Theory GCD, LCM, and Coprimality

Throughout this subsection II.B, we fix two natural integers $m$ and $n$. Let $g > 0$ be the $\gcd$ of $m$ and $n$. We set $m_1 = m/g$ and $n_1 = n/g$.
a) Show that if $m_1$ and $n_1$ are odd, then $T_g$ is a $\gcd$ of $T_n$ and $T_m$.
b) Show that if one of the two integers $m_1$ or $n_1$ is even, then $T_n$ and $T_m$ are coprime.
c) What can be said about the gcds of $T_n$ and $T_m$ when $m$ and $n$ are odd? When $n$ and $m$ are two distinct powers of 2?

Throughout this subsection II.B, we fix two natural integers $m$ and $n$. Let $g > 0$ be the $\gcd$ of $m$ and $n$. We set $m_1 = m/g$ and $n_1 = n/g$.

a) Show that if $m_1$ and $n_1$ are odd, then $T_g$ is a $\gcd$ of $T_n$ and $T_m$.

b) Show that if one of the two integers $m_1$ or $n_1$ is even, then $T_n$ and $T_m$ are coprime.

c) What can be said about the gcds of $T_n$ and $T_m$ when $m$ and $n$ are odd? When $n$ and $m$ are two distinct powers of 2?

Paper Questions

QI.A.1 QI.A.2 QI.A.3 QI.A.4 QI.B.1 QI.B.2 QII.A.1 QII.A.2 QII.B.1 QII.B.2 QIII.A.1 QIII.A.2 QIII.B.1 QIII.B.2 QIII.B.3 QIII.B.4 QIII.C.1 QIII.C.2 QIV.A QIV.B QIV.C.1 QIV.C.2 QIV.C.3 QIV.C.4