Exercise 4 (5 points) -- Candidate who has followed the specialization course

Numbers of the form $2^n - 1$ where $n$ is a non-zero natural number are called Mersenne numbers.

1. We denote by $a$, $b$ and $c$ three non-zero natural numbers such that $\operatorname{GCD}(b\,;\,c) = 1$.
   Prove, using Gauss's theorem, that: if $b$ divides $a$ and $c$ divides $a$ then the product $bc$ divides $a$.
2. We consider the Mersenne number $2^{33} - 1$.
   A student uses his calculator and obtains the results below:
   

   $\left(2^{33}-1\right) \div 3$	2863311530
   $\left(2^{33}-1\right) \div 4$	2147483648
   $\left(2^{33}-1\right) \div 12$	715827882.6

   
   He claims that 3 divides $\left(2^{33}-1\right)$ and 4 divides $\left(2^{33}-1\right)$ and 12 does not divide $\left(2^{33}-1\right)$. a. How does this claim contradict the result proved in question 1? b. Justify that, in reality, 4 does not divide $\left(2^{33}-1\right)$. c. By noting that $2 \equiv -1\ [3]$, show that, in reality, 3 does not divide $2^{33}-1$. d. Calculate the sum $S = 1 + 2^3 + \left(2^3\right)^2 + \left(2^3\right)^3 + \cdots + \left(2^3\right)^{10}$. e. Deduce that 7 divides $2^{33}-1$.
3. We consider the Mersenne number $2^7 - 1$. Is it prime? Justify.
4. We are given the following algorithm where $\operatorname{MOD}(N,k)$ represents the remainder of the Euclidean division of $N$ by $k$:
   

   Variables:

   $n$ natural number greater than or equal to 3

   $k$ natural number greater than or equal to 2

   Initialization:

   Ask the user for the value of $n$.

   Assign to $k$ the value 2.

   Processing:

   While $\operatorname{MOD}\left(2^n - 1,\,k\right) \neq 0$ and $k \leqslant \sqrt{2^n - 1}$

   Assign to $k$ the value $k+1$

   End While.

   Output:

   Otherwise

   Display ``CASE 2''

   End If

   
   a. What does this algorithm display if we enter $n = 33$? And if we enter $n = 7$? b. What does CASE 2 correspond to?

What is the smallest positive integer $n$ for which $\frac { 50 ! } { 24 ^ { n } }$ is not an integer?

For a natural number $m$, define $\Phi_{1}(m)$ to be the number of divisors of $m$ and for $k \geq 2$ define $\Phi_{k}(m) := \Phi_{1}\left(\Phi_{k-1}(m)\right)$. For example, $\Phi_{2}(12) = \Phi_{1}(6) = 4$. Find the minimum $k$ such that $$\Phi_{k}\left(2019^{2019}\right) = 2.$$

For a positive integer $n$, let $D(n) =$ number of positive integer divisors of $n$. For example, $D(6) = 4$ because 6 has four divisors, namely $1, 2, 3$ and $6$. Find the number of $n \leq 60$ such that $D(n) = 6$.

An integer $d$ is called a factor of an integer $n$ if there is an integer $q$ such that $n = qd$. In particular the set of factors of $n$ contains $n$ and contains 1. You are given that $2024 = 8 \times 11 \times 23$.
Write the number of even positive integers that are factors of $2024^2$. [2 points]

Let $n \in \mathbb{N}^*$. Show that for all $k \in \mathbb{N}^*$, $$\left(\frac{n}{n+k}\right)^k \leqslant \frac{n! n^k}{(n+k)!} \leqslant 1.$$

Show that, for every natural integer $n$, $$C_{n} = \frac{(2n)!}{(n+1)! \, n!}$$

Show that, for every natural integer $n$, $$C_{n} = \frac{(2n)!}{(n+1)! \, n!}$$

Let $(\Omega, \mathscr{A}, P)$ be a probability space. If $N \in \mathbb{N}^*$ and $p$ is a prime number, we denote by $\nu_p(N)$ the $p$-adic valuation of $N$. For $n \in \mathbb{N}^*$, we define the map $$\psi_n : \mathbb{N}^* \longrightarrow \mathbb{N}^*, \quad x \longmapsto \prod_{i=1}^{n} p_i^{\nu_{p_i}(x)}$$ where $(p_i)_{i \in \mathbb{N}^*}$ is the sequence of prime numbers, ordered in increasing order.
Let $X$ be a random variable defined on $(\Omega, \mathscr{A}, P)$ and taking values in $\mathbb{N}^*$. Show that $$\forall x \in \mathbb{N}^*, \quad P(X = x) = \lim_{n \rightarrow +\infty} P(\psi_n(X) = x).$$

If $N \in \mathbb{N}^*$ and $p$ is a prime number, we denote $\nu_p(N)$ the $p$-adic valuation of $N$. For $n \in \mathbb{N}^*$, we define the application $$\psi_n : \mathbb{N}^* \longrightarrow \mathbb{N}^*, \quad x \longmapsto \prod_{i=1}^{n} p_i^{\nu_{p_i}(x)}$$ where $(p_i)_{i \in \mathbb{N}^*}$ is the sequence of prime numbers, ordered in increasing order. Let $X$ be a random variable defined on $(\Omega, \mathscr{A}, P)$ and taking values in $\mathbb{N}^*$. Show that $$\forall x \in \mathbb{N}^*, \quad \mathbf{P}(X = x) = \lim_{n \rightarrow +\infty} \mathbf{P}(\psi_n(X) = x)$$

Show that $h(x) = \sum_{n=0}^{\infty} \frac{(2n)!(3n)!}{(n!)^5} x^n$ has integer coefficients.

Let $D$ be a common denominator of the rational numbers $a_1, \ldots, a_r$ and let $A = \max(1, |a_1|, \ldots, |a_r|)$. Show that $D^n u_n \in \mathbf{Z}$ for all $n \geq 0$.

Let $C = 1 + |s_1| + \cdots + |s_r|$. Show that $D^n v_n(k) \in \mathbf{Z}$ and that there exists a real number $c_2 > 0$ such that $$|v_n(k)| \leq c_2 A^n C^k \text{ for all } n \geq kr.$$

Deduce that $k!$ divides $D^n v_n(k)$ for all $n$ and $k$ such that $n \geq kr$.

Let $n$ be a non-zero natural integer and let $p$ be a prime number. Justify the formula $\nu_{p}(n!) = \sum_{k=1}^{+\infty} E\left(\frac{n}{p^{k}}\right)$ and show that $$\frac{n}{p} - 1 < \nu_{p}(n!) \leqslant \frac{n}{p} + \frac{n}{p(p-1)}$$

Let $n$ be a non-zero natural integer and let $p$ be a prime number. Justify the formula $\nu_p(n!) = \sum_{k=1}^{+\infty} E\left(\frac{n}{p^k}\right)$ and show that $$\frac{n}{p} - 1 < \nu_p(n!) \leqslant \frac{n}{p} + \frac{n}{p(p-1)}$$

Let $p$ be a prime number. Show that, for all $n \in \mathbb { N }$,
$$v _ { p } ( n ! ) = \sum _ { k = 1 } ^ { + \infty } \left\lfloor \frac { n } { p ^ { k } } \right\rfloor$$

Deduce that, for all $n \in \mathbb { N } ^ { * } , k \in \mathbb { N }$ and $p$ prime number: if $p ^ { k }$ divides $\binom { 2 n } { n }$, then $p ^ { k } \leqslant 2 n$.

The sum of all even positive divisors of $1000$ is
(a) $2170$
(b) $2184$
(c) $2325$
(d) $2340$

Among all the factors of $4 ^ { 6 } 6 ^ { 7 } 21 ^ { 8 }$, the number of factors which are perfect squares is
(a) 240
(b) 360
(c) 400
(d) 640

Let $P = \{2^a \cdot 3^b : 0 \leq a, b \leq 5\}$. Find the largest $n$ such that $2^n$ divides some element of $P$.
(A) $n = 20$ (B) $n = 22$ (C) $n = 24$ (D) $n = 26$

Let $a _ { n } = \underbrace{1 \ldots 1}_{3^n \text{ digits}}$ with $3 ^ { n }$ digits. Prove that $a _ { n }$ is divisible by $3 a _ { n - 1 }$.

Let $a _ { n } = 1 \ldots 1$ with $3 ^ { n }$ digits. Prove that $a _ { n }$ is divisible by $3 a _ { n - 1 }$.

Let $n _ { 1 } , n _ { 2 } , \cdots , n _ { 51 }$ be distinct natural numbers each of which has exactly 2023 positive integer factors. For instance, $2 ^ { 2022 }$ has exactly 2023 positive integer factors $1,2,2 ^ { 2 } , \cdots , 2 ^ { 2021 } , 2 ^ { 2022 }$. Assume that no prime larger than 11 divides any of the $n _ { i }$'s. Show that there must be some perfect cube among the $n _ { i }$'s. You may use the fact that $2023 = 7 \times 17 \times 17$.

The number of consecutive zeroes adjacent to the digit in the unit's place of $401 ^ { 50 }$ is
(A) 3.
(B) 4.
(C) 49.
(D) 50.