grandes-ecoles 2025 Q11

grandes-ecoles · France · x-ens-maths-d__mp Number Theory Linear Diophantine Equations
Let $k \in \mathbb{N}^*$ and $(a_1, \ldots, a_k) \in (\mathbb{N}^*)^k$ a $k$-tuple of strictly positive integers. When $k \geq 2$, we assume they are coprime as a set. We define a function $P : \mathbb{N} \rightarrow \mathbb{C}$ by setting for all $n \in \mathbb{N}$: $$P(n) = \operatorname{Card}\left\{(n_1, \ldots, n_k) \in \mathbb{N}^k : n_1 a_1 + \cdots + n_k a_k = n\right\}.$$ We assume $k = 2$. Prove that $$P(n) = \frac{n}{ab} - \left\{\frac{b^* n}{a}\right\} - \left\{\frac{a^* n}{b}\right\} + 1$$ for all integer $n \geq 0$, where $a^*$ and $b^*$ are integers satisfying $a^* a = 1$ modulo $b$ and $b^* b = 1$ modulo $a$ respectively.
Hint. One may use the formula $(*)$ for $b = 1$.
Let $k \in \mathbb{N}^*$ and $(a_1, \ldots, a_k) \in (\mathbb{N}^*)^k$ a $k$-tuple of strictly positive integers. When $k \geq 2$, we assume they are coprime as a set. We define a function $P : \mathbb{N} \rightarrow \mathbb{C}$ by setting for all $n \in \mathbb{N}$:
$$P(n) = \operatorname{Card}\left\{(n_1, \ldots, n_k) \in \mathbb{N}^k : n_1 a_1 + \cdots + n_k a_k = n\right\}.$$
We assume $k = 2$. Prove that
$$P(n) = \frac{n}{ab} - \left\{\frac{b^* n}{a}\right\} - \left\{\frac{a^* n}{b}\right\} + 1$$
for all integer $n \geq 0$, where $a^*$ and $b^*$ are integers satisfying $a^* a = 1$ modulo $b$ and $b^* b = 1$ modulo $a$ respectively.

\textit{Hint.} One may use the formula $(*)$ for $b = 1$.