En raison de limitations techniques, la typographie souhaitable du titre, «
Exercice : CongruencesArithmétique/Exercices/Congruences », n'a pu être restituée correctement ci-dessus.
Quel est le reste de la division par 7 du nombre 3245 ?
Solution
Modulo 7,
32
3
≡
(
−
3
)
3
=
−
27
≡
1
{\displaystyle 32^{3}\equiv (-3)^{3}=-27\equiv 1}
donc
32
3
×
15
≡
1
15
=
1
{\displaystyle 32^{3\times 15}\equiv 1^{15}=1}
: le reste est donc 1.
Quel est le reste de la division par 19 du nombre 57383114 ?
Solution
57383
=
3020
×
19
+
3
{\displaystyle 57383=3020\times 19+3}
et modulo 19,
3
9
≡
−
1
{\displaystyle 3^{9}\equiv -1}
donc
57383
114
≡
3
9
×
12
+
6
≡
3
6
≡
8
2
≡
7
{\displaystyle 57383^{114}\equiv 3^{9\times 12+6}\equiv 3^{6}\equiv 8^{2}\equiv 7}
: le reste est 7.
Quel est le reste de la division par 7 du nombre 912341998 ?
Solution
91234
=
13033
×
7
+
3
{\displaystyle 91234=13033\times 7+3}
,
3
3
≡
−
1
(
mod
7
)
{\displaystyle 3^{3}\equiv -1{\pmod {7}}}
et
6
∣
1998
{\displaystyle 6\mid 1998}
, donc le reste est 1.
Démontrez que si l'on divise un entier n par 111, on trouve le même reste qu'en divisant 1000n par 111.
Déduisez-en que les deux nombres 108 + 104 + 1 et 1010 + 105 + 1 sont divisibles par 111.
Quels sont les entiers n tels que n 6 – 1 soit divisible par 9 ?
Solution
Modulo 9, n 3 est congru à 0 si n est divisible par 3, et à ±1 sinon. Les solutions sont donc tous les entiers non divisibles par 3.
Soient n 1 , n 2 , n 3 , n 4 et n 5 cinq entiers relatifs vérifiant la relation :
n
1
3
+
n
2
3
+
n
3
3
+
n
4
3
+
n
5
3
=
0
{\displaystyle n_{1}^{3}+n_{2}^{3}+n_{3}^{3}+n_{4}^{3}+n_{5}^{3}=0}
.
Montrez qu'alors, au moins un de ces cinq entiers est un multiple de 7.
Démontrer que si les entiers p et 8p – 1 sont premiers, alors 8p + 1 n'est pas premier. (Aide : On s'aidera des congruences modulo 3.)
Démontrer que si p est premier et différent de 3, alors 8p 2 + 1 est composé.
Solution
Si p = 3, 8p + 1 = 25. Si p est premier et différent de 3, alors, modulo 3, p ≡ ±1 donc (8p – 1)(8p + 1) ≡ (–p – 1)(–p + 1) = p 2 – 1 ≡ 0.
Si p est premier et différent de 3, alors, modulo 3, p ≡ ±1 donc 8p 2 + 1 ≡ 9 ≡ 0.
Trouvez tous les entiers relatifs
x
{\displaystyle x}
vérifiant simultanément les trois congruences :
{
x
≡
1
(
mod
2
)
x
≡
2
(
mod
3
)
x
≡
3
(
mod
4
)
.
{\displaystyle {\begin{cases}x\equiv 1{\pmod {2}}\\x\equiv 2{\pmod {3}}\\x\equiv 3{\pmod {4}}.\end{cases}}}
Déterminer le chiffre des unités de
7
7
7
{\displaystyle 7^{7^{7}}}
.
Solution
Modulo 10,
7
4
≡
(
−
1
)
2
=
1
{\displaystyle 7^{4}\equiv (-1)^{2}=1}
et modulo 4,
7
7
≡
(
−
1
)
7
≡
−
1
≡
3
{\displaystyle 7^{7}\equiv (-1)^{7}\equiv -1\equiv 3}
donc modulo 10,
7
7
7
≡
7
3
≡
−
7
≡
3
{\displaystyle 7^{7^{7}}\equiv 7^{3}\equiv -7\equiv 3}
: le chiffre est 3.
Wikipedia-logo-v2.svg
Trouvez tous les entiers congrus à la fois à
1
mod
13
{\displaystyle 1{\bmod {13}}}
et à
6
mod
7
{\displaystyle 6{\bmod {7}}}
.
Trouvez tous les entiers congrus à la fois à
5
mod
8
{\displaystyle 5{\bmod {8}}}
et à
1
mod
27
{\displaystyle 1{\bmod {27}}}
.
Trouvez tous les entiers congrus à la fois à
1
mod
4
{\displaystyle 1{\bmod {4}}}
et à
±
1
mod
5
{\displaystyle \pm 1{\bmod {5}}}
.
Trouvez tous les entiers congrus à la fois à
3
mod
4
{\displaystyle 3{\bmod {4}}}
et à
±
2
mod
5
{\displaystyle \pm 2{\bmod {5}}}
.
Trouvez tous les entiers congrus à la fois à
1
mod
3
{\displaystyle 1{\bmod {3}}}
et à
±
1
mod
8
{\displaystyle \pm 1{\bmod {8}}}
.
Trouvez tous les entiers congrus à la fois à
−
1
mod
3
{\displaystyle -1{\bmod {3}}}
et à
±
3
mod
8
{\displaystyle \pm 3{\bmod {8}}}
.
Trouvez tous les entiers congrus à la fois à
±
2
mod
5
{\displaystyle \pm 2{\bmod {5}}}
et à
±
5
mod
13
{\displaystyle \pm 5{\bmod {13}}}
.
Trouvez tous les entiers congrus à la fois à
1
{\displaystyle 1}
ou
3
mod
8
{\displaystyle 3{\bmod {8}}}
et à
±
1
mod
5
{\displaystyle \pm 1{\bmod {5}}}
.
Trouvez tous les entiers congrus à la fois à
−
1
{\displaystyle -1}
ou
−
3
mod
8
{\displaystyle -3{\bmod {8}}}
et à
±
2
mod
5
{\displaystyle \pm 2{\bmod {5}}}
.
Solution
Soit
n
=
13
k
+
1
{\displaystyle n=13k+1}
. Puisque
13
≡
6
≡
−
1
mod
7
{\displaystyle 13\equiv 6\equiv -1{\bmod {7}}}
,
n
≡
6
mod
7
⇔
−
k
+
1
≡
−
1
mod
7
⇔
k
≡
2
mod
7
{\displaystyle n\equiv 6{\bmod {7}}\Leftrightarrow -k+1\equiv -1{\bmod {7}}\Leftrightarrow k\equiv 2{\bmod {7}}}
donc les solutions sont :
n
=
13
(
7
l
+
2
)
+
1
=
91
l
+
27
{\displaystyle n=13\left(7l+2\right)+1=91l+27}
, avec
l
∈
Z
{\displaystyle l\in \mathbb {Z} }
.
Soit
n
=
27
k
+
1
{\displaystyle n=27k+1}
. Alors,
n
≡
5
mod
8
⇔
3
k
+
1
≡
−
3
mod
8
⇔
3
k
≡
−
12
mod
8
⇔
k
≡
−
4
mod
8
{\displaystyle n\equiv 5{\bmod {8}}\Leftrightarrow 3k+1\equiv -3{\bmod {8}}\Leftrightarrow 3k\equiv -12{\bmod {8}}\Leftrightarrow k\equiv -4{\bmod {8}}}
donc les solutions sont :
n
=
27
(
8
l
−
4
)
+
1
=
216
l
−
107
{\displaystyle n=27\left(8l-4\right)+1=216l-107}
, avec
l
∈
Z
{\displaystyle l\in \mathbb {Z} }
.
Soit
n
=
4
k
+
1
{\displaystyle n=4k+1}
. Alors,
n
≡
±
1
mod
5
⇔
−
k
+
1
≡
±
1
mod
5
⇔
k
≡
0
ou
2
mod
5
{\displaystyle n\equiv \pm 1{\bmod {5}}\Leftrightarrow -k+1\equiv \pm 1{\bmod {5}}\Leftrightarrow k\equiv 0{\text{ ou }}2{\bmod {5}}}
.
Les solutions sont donc les entiers
n
{\displaystyle n}
de la forme
n
=
4
(
5
l
)
+
1
=
20
l
+
1
{\displaystyle n=4\left(5l\right)+1=20l+1}
et ceux de la forme
n
=
4
(
5
l
+
2
)
+
1
=
20
l
+
9
{\displaystyle n=4\left(5l+2\right)+1=20l+9}
, c'est-à-dire les entiers congrus à
1
ou
9
mod
20
{\displaystyle 1{\text{ ou }}9{\bmod {20}}}
.
Soit
n
=
4
k
−
1
{\displaystyle n=4k-1}
. Alors,
n
≡
±
2
mod
5
⇔
−
k
−
1
≡
±
2
mod
5
⇔
k
≡
−
3
ou
1
mod
5
⇔
k
≡
1
ou
2
mod
5
{\displaystyle n\equiv \pm 2{\bmod {5}}\Leftrightarrow -k-1\equiv \pm 2{\bmod {5}}\Leftrightarrow k\equiv -3{\text{ ou }}1{\bmod {5}}\Leftrightarrow k\equiv 1{\text{ ou }}2{\bmod {5}}}
.
Les solutions sont donc les entiers
n
{\displaystyle n}
de la forme
n
=
4
(
5
l
+
1
)
−
1
=
20
l
+
3
{\displaystyle n=4\left(5l+1\right)-1=20l+3}
et ceux de la forme
n
=
4
(
5
l
+
2
)
−
1
=
20
l
+
7
{\displaystyle n=4\left(5l+2\right)-1=20l+7}
, c'est-à-dire les entiers congrus à
3
ou
7
mod
20
{\displaystyle 3{\text{ ou }}7{\bmod {20}}}
.
Soit
n
=
3
k
+
1
{\displaystyle n=3k+1}
. Alors,
n
≡
±
1
mod
8
⇔
3
k
≡
0
ou
−
2
mod
8
⇔
3
k
≡
0
ou
6
mod
8
⇔
k
≡
0
ou
2
mod
8
{\displaystyle n\equiv \pm 1{\bmod {8}}\Leftrightarrow 3k\equiv 0{\text{ ou }}-2{\bmod {8}}\Leftrightarrow 3k\equiv 0{\text{ ou }}6{\bmod {8}}\Leftrightarrow k\equiv 0{\text{ ou }}2{\bmod {8}}}
.
Les solutions sont donc les entiers
n
{\displaystyle n}
de la forme
n
=
3
(
8
l
)
+
1
=
24
l
+
1
{\displaystyle n=3\left(8l\right)+1=24l+1}
et ceux de la forme
n
=
3
(
8
l
+
2
)
+
1
=
24
l
+
7
{\displaystyle n=3\left(8l+2\right)+1=24l+7}
, c'est-à-dire les entiers congrus à
1
ou
7
mod
24
{\displaystyle 1{\text{ ou }}7{\bmod {24}}}
.
Soit
n
=
3
k
−
1
{\displaystyle n=3k-1}
. Alors,
n
≡
±
3
mod
8
⇔
3
k
≡
−
2
ou
4
mod
8
⇔
3
k
≡
6
ou
12
mod
8
⇔
k
≡
2
ou
4
mod
8
{\displaystyle n\equiv \pm 3{\bmod {8}}\Leftrightarrow 3k\equiv -2{\text{ ou }}4{\bmod {8}}\Leftrightarrow 3k\equiv 6{\text{ ou }}12{\bmod {8}}\Leftrightarrow k\equiv 2{\text{ ou }}4{\bmod {8}}}
.
Les solutions sont donc les entiers
n
{\displaystyle n}
de la forme
n
=
3
(
8
l
+
2
)
−
1
=
24
l
+
5
{\displaystyle n=3\left(8l+2\right)-1=24l+5}
et ceux de la forme
n
=
3
(
8
l
+
4
)
−
1
=
24
l
+
11
{\displaystyle n=3\left(8l+4\right)-1=24l+11}
, c'est-à-dire les entiers congrus à
5
ou
11
mod
24
{\displaystyle 5{\text{ ou }}11{\bmod {24}}}
.
Soit
n
=
13
k
+
5
ε
{\displaystyle n=13k+5\varepsilon }
, avec
ε
=
±
1
{\displaystyle \varepsilon =\pm 1}
. Alors,
n
≡
±
2
mod
5
⇔
−
2
k
≡
±
2
mod
5
⇔
k
≡
±
1
mod
5
{\displaystyle n\equiv \pm 2{\bmod {5}}\Leftrightarrow -2k\equiv \pm 2{\bmod {5}}\Leftrightarrow k\equiv \pm 1{\bmod {5}}}
.
Les solutions sont donc les entiers
n
{\displaystyle n}
de la forme
n
=
13
(
5
l
+
ε
)
+
5
ε
=
65
l
+
18
ε
{\displaystyle n=13\left(5l+\varepsilon \right)+5\varepsilon =65l+18\varepsilon }
et ceux de la forme
n
=
13
(
5
l
−
ε
)
+
5
ε
=
65
l
−
8
ε
{\displaystyle n=13\left(5l-\varepsilon \right)+5\varepsilon =65l-8\varepsilon }
avec
ε
=
±
1
{\displaystyle \varepsilon =\pm 1}
, c'est-à-dire les entiers congrus à
±
8
ou
±
18
mod
65
{\displaystyle \pm 8{\text{ ou }}\pm {18}{\bmod {65}}}
.
Soit d'abord
n
=
8
k
+
1
{\displaystyle n=8k+1}
. Alors,
n
≡
±
1
mod
5
⇔
−
2
k
≡
0
ou
−
2
mod
5
⇔
k
≡
0
ou
1
mod
5
{\displaystyle n\equiv \pm 1{\bmod {5}}\Leftrightarrow -2k\equiv 0{\text{ ou }}-2{\bmod {5}}\Leftrightarrow k\equiv 0{\text{ ou }}1{\bmod {5}}}
. Soit d'autre part
n
=
8
k
+
3
{\displaystyle n=8k+3}
. Alors,
n
≡
±
1
mod
5
⇔
−
2
k
≡
−
2
ou
−
4
mod
5
⇔
k
≡
1
ou
2
mod
5
{\displaystyle n\equiv \pm 1{\bmod {5}}\Leftrightarrow -2k\equiv -2{\text{ ou }}-4{\bmod {5}}\Leftrightarrow k\equiv 1{\text{ ou }}2{\bmod {5}}}
.
Les solutions sont donc les entiers
n
{\displaystyle n}
de la forme
n
=
8
(
5
l
)
+
1
=
40
l
+
1
{\displaystyle n=8\left(5l\right)+1=40l+1}
,
n
=
8
(
5
l
+
1
)
+
1
=
40
l
+
9
{\displaystyle n=8\left(5l+1\right)+1=40l+9}
,
n
=
8
(
5
l
+
1
)
+
3
=
40
l
+
11
{\displaystyle n=8\left(5l+1\right)+3=40l+11}
ou
n
=
8
(
5
l
+
2
)
+
3
=
40
l
+
19
{\displaystyle n=8\left(5l+2\right)+3=40l+19}
, c'est-à-dire les entiers congrus à
1
,
9
,
11
ou
19
mod
40
{\displaystyle 1,9,11{\text{ ou }}19{\bmod {40}}}
.
Soit d'abord
n
=
8
k
−
1
{\displaystyle n=8k-1}
. Alors,
n
≡
±
1
mod
5
⇔
−
2
k
≡
−
2
ou
4
mod
5
⇔
k
≡
1
ou
−
2
mod
5
{\displaystyle n\equiv \pm 1{\bmod {5}}\Leftrightarrow -2k\equiv -2{\text{ ou }}4{\bmod {5}}\Leftrightarrow k\equiv 1{\text{ ou }}-2{\bmod {5}}}
. Soit d'autre part
n
=
8
k
−
3
{\displaystyle n=8k-3}
. Alors,
n
≡
±
1
mod
5
⇔
−
2
k
≡
0
ou
−
4
mod
5
⇔
k
≡
0
ou
2
mod
5
{\displaystyle n\equiv \pm 1{\bmod {5}}\Leftrightarrow -2k\equiv 0{\text{ ou }}-4{\bmod {5}}\Leftrightarrow k\equiv 0{\text{ ou }}2{\bmod {5}}}
.
Les solutions sont donc les entiers
n
{\displaystyle n}
de la forme
n
=
8
(
5
l
+
1
)
−
1
=
40
l
+
7
{\displaystyle n=8\left(5l+1\right)-1=40l+7}
,
n
=
8
(
5
l
−
2
)
−
1
=
40
l
−
17
{\displaystyle n=8\left(5l-2\right)-1=40l-17}
,
n
=
8
(
5
l
)
−
3
=
40
l
−
3
{\displaystyle n=8\left(5l\right)-3=40l-3}
ou
n
=
8
(
5
l
+
2
)
−
3
=
40
l
+
13
{\displaystyle n=8\left(5l+2\right)-3=40l+13}
, c'est-à-dire les entiers congrus à
7
,
−
17
,
−
3
ou
13
mod
40
{\displaystyle 7,-17,-3{\text{ ou }}13{\bmod {40}}}
.
Montrer que pour tout entier naturel
n
{\displaystyle n}
,
5
∣
(
2
3
n
+
5
+
3
n
+
1
)
{\displaystyle 5\mid (2^{3n+5}+3^{n+1})}
.
Quel est le reste de la division euclidienne de
16
(
2
1000
)
{\displaystyle 16^{(2^{1000})}}
par
7
{\displaystyle 7}
?
Soit
n
{\displaystyle n}
un entier impair non divisible par
3
{\displaystyle 3}
. Montrer que
n
2
≡
1
mod
24
{\displaystyle n^{2}\equiv 1{\bmod {24}}}
.
Donner le dernier chiffre de l'écriture en base
10
{\displaystyle 10}
de
∑
k
=
0
10
k
100
{\displaystyle \sum _{k=0}^{10}k^{100}}
.