bac-s-maths 2013 Q2b

bac-s-maths · France · amerique-nord 5 marks Number Theory Modular Arithmetic Computation
Exercise 2 — Candidates WHO HAVE FOLLOWED the mathematics specialization course
Part A
We consider the following algorithm:
Variables :$a$ is a natural integer $b$ is a natural integer $c$ is a natural integer
Initialization :Assign to $c$ the value 0 Request the value of $a$ Request the value of $b$
Processing :While $a > b$ Assign to $c$ the value $c + 1$ Assign to $a$ the value $a - b$ End of while
Output :Display $c$ Display $a$

  1. Run this algorithm with $a = 13$ and $b = 4$ by indicating the values of the variables at each step.
  2. What does this algorithm allow us to calculate?

Part B
To each letter of the alphabet, we associate, using the table below, an integer between 0 and 25.
ABCDEFGHIJKLM
0123456789101112
NOPQRSTUVWXYZ
13141516171819202122232425

We define an encoding process as follows: Step 1: To the letter we want to encode, we associate the corresponding number $m$ in the table. Step 2: We calculate the remainder of the Euclidean division of $9 m + 5$ by 26 and denote it $p$. Step 3 : To the number $p$, we associate the corresponding letter in the table.
  1. Encode the letter U.
  2. Modify the algorithm from Part A so that for a value of $m$ entered by the user, it displays the value of $p$, calculated using the above encoding process.

Part C
  1. Find an integer $x$ such that $9 x \equiv 1$ [26].
  2. Then prove the equivalence: $$9 m + 5 \equiv p \quad [ 26 ] \Longleftrightarrow m \equiv 3 p - 15$$
  3. Then decode the letter B. 
\textbf{Exercise 2 — Candidates WHO HAVE FOLLOWED the mathematics specialization course}

\section*{Part A}
We consider the following algorithm:

\begin{center}
\begin{tabular}{|l|l|}
\hline
Variables : & $a$ is a natural integer $b$ is a natural integer $c$ is a natural integer \\
\hline
Initialization : & Assign to $c$ the value 0 Request the value of $a$ Request the value of $b$ \\
\hline
Processing : & While $a > b$ Assign to $c$ the value $c + 1$ Assign to $a$ the value $a - b$ End of while \\
\hline
Output : & Display $c$ Display $a$ \\
\hline
\end{tabular}
\end{center}

\begin{enumerate}
  \item Run this algorithm with $a = 13$ and $b = 4$ by indicating the values of the variables at each step.
  \item What does this algorithm allow us to calculate?
\end{enumerate}

\section*{Part B}
To each letter of the alphabet, we associate, using the table below, an integer between 0 and 25.

\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | c | c | c | c | c | c | c | }
\hline
A & B & C & D & E & F & G & H & I & J & K & L & M \\
\hline
0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\
\hline\hline
N & O & P & Q & R & S & T & U & V & W & X & Y & Z \\
\hline
13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24 & 25 \\
\hline
\end{tabular}
\end{center}

We define an encoding process as follows:\\
Step 1: To the letter we want to encode, we associate the corresponding number $m$ in the table.\\
Step 2: We calculate the remainder of the Euclidean division of $9 m + 5$ by 26 and denote it $p$.\\
Step 3 : To the number $p$, we associate the corresponding letter in the table.

\begin{enumerate}
  \item Encode the letter U.
  \item Modify the algorithm from Part A so that for a value of $m$ entered by the user, it displays the value of $p$, calculated using the above encoding process.
\end{enumerate}

\section*{Part C}
\begin{enumerate}
  \item Find an integer $x$ such that $9 x \equiv 1$ [26].
  \item Then prove the equivalence:
$$9 m + 5 \equiv p \quad [ 26 ] \Longleftrightarrow m \equiv 3 p - 15$$
  \item Then decode the letter B.
\end{enumerate}
Paper Questions
Q1 Q2a Q2b Q3 Q4