Approfondissements de lycée/PS Premiers

Un livre de Wikibooks.

< Approfondissements de lycée(Redirigé depuis AL PS Premiers)

[modifier] Question 1

Montrer que le théorème "divisible par 3" marche pour tout nombre à 3 chiffres (Astuce : Exprimer un nombre à 3 chiffre sous la forme 100a + 10b + c, où 0 ≤ a, b et c ≤ 9)

[modifier] Solution 1

Tout nombre entier à 3 chiffre x peut être exprimé comme suit

x = 100a + 10b + c

où a, b et c sont des entiers positifs compris entre 0 et 9. Maintenant,

$x \equiv 100a + 10b + c \equiv a + b + c \pmod{3}$

$x \equiv 0 \pmod{3}$

si et seulement si a + b + c = 3k pour un certain k. Mais a, b et c sont les chiffres de x.

[modifier] Question 2

"Un nombre est divisible par 9 si et seulement si la somme est divisible par 9." Vrai ou faux ? Déterminer si 89, 558, 51858, et 41857 sont divisibles par 9. Vérifier vos réponses.

[modifier] Solution 2

Le résultat est vrai et peut être démontré comme dans la question 1.

[modifier] Question 3

Existe-t'il une règle pour déterminer si un nombre à 3 chiffres est divisible par 11 ? Si oui, déterminer cette règle.

[modifier] Solution 3

Comme précédement

x = 100a + 10b + c

Maintenant

$x \equiv a + 10b + c \equiv a - b + c \pmod{11}$

Un nombre à trois chiffres est divisible par 11 si et seulement si la somme de son premier et dernier chiffre moins le second est divisible par 11.

[modifier] Question 4

$\begin{matrix} X & 2 & 3 & X & 5 &X &7& X& X& X \\ 11 & X & 13 & X& X& X&17 &X& 19& X\\ X& X& 23 & X& X &X&X&X&29& X\\ 31 &X& X& X& X &X&37& X& X& X\\ 41 & X& 43 & X& X&X&47& X& 49& X\\ \end{matrix}$

Le crible premier a été appliqué à la table ci-dessus. Noter que chaque nombre situé directement sous 2 et 5 sont rayés. Construire une grille rectangulaire de nombre allant de 1 à 60 après que le crible premier ait été exécuté sur elle, tous les nombres situés directement sous 3 et 5 sont rayés. Quelle est la largeur de la grille ?

[modifier] Solution 4

La largeur de la grille est 15 ou un multiple de celui-ci.

[modifier] Question 5

Montrer que p, p + 2 et p + 4 ne peuvent pas être tous des nombres premiers. (p un nombre entier positif)

[modifier] Solution 5

Plaçons-nous en arithmétique mod 3, alors p peut être mis dans une des trois catégories

1ère catégorie

$p \equiv 0 \pmod{3}$

p n'est pas premier

2ème catégorie

$p \equiv 1 \pmod{3}$

$p + 2\equiv 0 \pmod{3}$

p + 2 n'est pas premier

3ème catégorie

$p \equiv 2 \pmod{3}$

$p + 4\equiv 0 \pmod{3}$

p + 4 n'est pas premier

Par conséquent p, p + 2 et p + 4 ne peuvent pas être tous premiers.

[modifier] Question 6

Montrer que n - 1 a lui-même comme inverse modulo n.

[modifier] Solution 6

(n - 1)² = n² - 2n + 1 = 1 (mod n)

Alternativement

(n - 1)² = (-1)² = 1 (mod n)

[modifier] Question 7

Montrer que 10 n'a pas d'inverse modulo 15.

[modifier] Solution 7

Supposons que 10 possède un inverse x mod 15,

10x = 1 (mod 15)

2 x 5x = 1 (mod 15)

5x = 8 (mod 15)

5x = 8 + 15k

pour un certain entier k

x = 1,6 + 3k

mais maintenant, x n'est pas un entier, par conséquent 10 n'a pas d'inverse

[modifier] Question 8

Trouver x

$\begin{matrix} x \equiv 3^7 + 1^7 + 2^7 + + 4^7 + 5^7 + 6^7 + 7^7 \ \pmod{7}\\ \end{matrix}$

[modifier] Solution 8

Notons que

$-a \equiv 7-a \pmod 7$ .

Alors

$1^7 \equiv (7-6)^7 \equiv (-6)^7 \equiv -(6^7) \pmod 7$ .

De même,

$2^7 \equiv -5^7 \pmod 7$

et

$3^7 \equiv -4^7 \pmod 7$ .

Alors

$\begin{matrix} x &\equiv& 1^7 + 2^7 + 3^7 + 4^7 + 5^7 + 6^7 + 7^7 &\\ &\equiv& 1^7 + 2^7 + 3^7 - 3^7 - 2^7 -1^7 + 7^7 &\\ &\equiv& 0 &\pmod{7} \\ \end{matrix}$

[modifier] Question 9

9. Montrer qu'il n'existe pas d'entier x et y tels que

x 2 - 5 y 2 = 3

[modifier] Solution 9

Regardons l'équation mod 5, nous avons

x 2 = 3(mod 5)

mais

$\begin{matrix} 1^2 = 1\\ 2^2 = 4\\ 3^2 = 9 = 4\\ 4^2 = 16 = 1 \end{matrix}$

Par conséquent, il n'existe pas de x tel que

x 2 = 3(mod 5)

[modifier] Question 10

Soit p un nombre premier. Montrer que

(a)

$(p-1)! \equiv -1\ \mbox{(mod p)}$

où

$n! = 1 \cdot 2 \cdot 3 \cdots (n-1) \cdot n$

C.a.d. 3! = 1*2*3 = 6

(b)

Maintenant, montrer que

$\sqrt{-1} \equiv \frac{p - 1}{2}! \pmod{p}$

pour p ≡ 1 (mod 4)

[modifier] Solution 10

a) Si p = 2, alors c'est évident. Donc, nous supposons que p est un nombre premier impair. Puisque p est premier, cela implique que chaque élément distinct possède un inverse et que l'inverse de (p - 1) est (p - 1). Puisque

(p - 1)! = (p - 1) [(p - 2)(p - 3)... 2]

vous pouvez apparier les inverses et les multiplier pour donner 1, et (p - 1) possède comme inverse lui-même, par conséquent, c'est le seul élément non-"éliminé"

(p - 1)! = (p - 1)

(p - 1)! = - 1

est requis.

b) A partir de a)

-1 = (p - 1)!

puique p = 4k + 1 pour un certain entier positif k, (p - 1)! possède 4k termes

-1 = 1 x 2 x 3 x... 2k x (-2k) x(- 3) x (- 2) x (- 1)

il existe un nombre pair de nombres négatifs pour le coté droit, donc

-1 = (1 x 2 x 3 x...2k)²

il s'ensuit

$\sqrt{-1} = 1\times 2\times 3\times ... 2k$

et finalement, nous notons que p = 4k + 1, nous pouvons conclure

$\sqrt{-1} = \frac{p - 1}{2}!$