Un carré modulo n

Un carré dans l'ensemble $\Z$ des entiers, c'est le carré d'un entier. Par exemple, $0^2$, $1^2$, $2^2$, $(-3)^2$, $6^2$ sont des carrés. Autrement dit, $0$, $1$, $4$, $9$ et $36$ sont des carrés. Pourquoi est-ce que $a=36$ est un carré ? Parce qu'il existe $b$ entier tel que $a=b^2$ : il suffit de prendre $b=6$.

Plus généralement, un entier $a$ est un carré s'il existe un entier $b$ tel que $a=b^2$.


Maintenant, on fixe un entier $n$, disons $n=11$, et au lieu de travailler chez les entiers, on travaille chez les entiers modulo $n$. Essentiellement, cela signifie que l'on travaille dans $\Z/n\Z$ – mais tu ne connais peut-être pas cette notation ? Modulo $n$, quels sont les valeurs possibles de $b^2$. Tu dois savoir que si on prend deux nombres $b$ et $b'$ congrus modulo $n$, leurs carrés sont aussi congrus modulo $n$, n'est-ce pas ? Il suffit donc de prendre $b$ entre $0$ et $10$.
\[\begin{array}{c|cccccccccc|}b&0&1&2&3&4&5&6&7&8&9&10\\\hline
b^2&0&1&4&9&16&25&36&49&64&81&100\\
b^2\pmod{11}&0&1&4&9&5&3&3&5&9&4&1\end{array}\]Il semble raisonnable de dire que $0$, $1$, $3$, $4$, $5$ et $9$ sont des carrés modulo $11$, n'est-ce pas ? Alors que $2$, $6$, $7$, $8$, $10$ n'en sont pas. Pourquoi est-ce que $3$ est un carré modulo $11$ ? Parce qu'il existe $b$, par exemple $b=5$, tel que $3=5^2\pmod{11}$.