a
Middle
School
Grade 6
Grade 7
Grade 8
Grade 9
Ressource
Out Middle
High
School
Grade 10
Grade 11
Grade 11 - STMG
Grade 12 - STMG
Grade 12
Grade 12 - Comp.
Grade 12 - Exp.
Ressource
Out High
4
3
2
1
Outside the high school program
/ Congruence
43 exercises (including 31 corrected)
a
Congruence
(15 exercices)
Congruence and power
(7 exercices)
Verification key problem
(4 exercices)
Coding
(4 exercices)
Property of gcd and cfcm
(3 exercices)
Fermat's little theorem
(8 exercices)
PPCM
(3 exercices)
1.
Congruenc
e
E.24
Let
abcd
=
1000
·
a
+100
·
b
+10
·
c
+
d
denote
a
base-10
in
teger
whose
digits
are
a
,
b
,
c
,
and
d
.
1
a
Find
the
remainder
when
100
is
divided
b
y
11,
and
then
when
1000
is
divided
b
y
11.
b
Sho
w
that
if
an
in
teger
n
satisfies
:
n
≡
10
(
mo
d.
11)
then
w
e
can
also
write
:
n
≡
−
1
(
mo
d.
11)
c
Conclude
that
if
abcd
is
divisible
b
y
11,
then
−
a
+
b
−
c
+
d
is
also
divisible
b
y
11.
2
a
Are
in
tegers
of
the
form
abba
divisible
b
y
11?
b
F
or
what
v
alue
of
a
is
the
in
teger
1
a
1
divisible
b
y
11?
c
F
or
what
v
alue
of
a
is
the
in
teger
9
a
9
divisible
b
y
11?
3
Under
what
conditions
are
in
tegers
of
the
form
aab
divis-
ible
b
y
11?
E.20
The
aim
of
this
exercise
is
to
demon-
strate
that,
for
an
y
non-zero
natural
n
um
b
er
n
,
the
in
teger
A
=
n
·
(
n
2
−
1)
is
a
m
ultiple
of
6.
1
In
eac
h
of
the
follo
wing
cases,
calculate
A
and
determine
the
remainder
in
the
Euclidean
division
of
A
b
y
6.
a
n
=
5
b
n
=
16
c
n
=
32
2
W
e
no
w
assume
that
the
remainder
of
the
Euclidean
di-
vision
of
n
b
y
6
is
5
;
w
e
can
therefore
write
:
N
≡
5
(
mo
d.
6)
.
a
What
can
w
e
conclude
for
(
n
−
1)
and
(
n
+1)
?
b
What
is
the
remainder
of
the
Euclidean
division
of
(
n
2
−
1)
b
y
6?
c
Then
justify
that
n
(
n
2
−
1)
is
a
m
ultiple
of
6.
3
Cop
y
and
complete
the
table
:
Rest
of
la
division
de
n
p
er
6
Rest
of
la
division
de
(
n
−
1)
par
6
Reste
de
la
division
de
(
n
+1)
par
6
Reste
de
la
division
de
(
n
2
−
1)
par
6
Rest
of
la
division
de
n
(
n
2
−
1)
par
6
0
1
2
3
2
4
2
0
4
5
4
Conclude.
E.27
1
a
Find
the
smallest
natural
in
tegers
a
,
b
,
c
v
erifying
:
100
≡
a
(
mo
d.
4)
;
27
≡
b
(
mo
d.
4)
;
95
≡
c
(
mo
d.
4)
b
Deduce
the
remainder
of
the
Euclidean
division
27
×
100
b
y
4.
Then,
the
remainder
of
2
795
b
y
4
2
a
Calculate
the
remainder
of
the
Euclidean
division
of
10
,
100
,
1000
b
y
9
.
b
Deduce
the
smallest
natural
in
tegers
a
,
b
,
c
v
erifying
:
3
×
1000
≡
A
(
mo
d.
9)
;
7
×
100
≡
B
(
mo
d.
9)
;
8
×
10
≡
C
(
mo
d.
9)
c
Giv
e
the
remainder
of
the
Euclidean
division
of
3
785
b
y
9
.
3
a
Using
a
metho
d
equiv
alen
t
to
that
in
question
2
,
giv
e
the
smallest
natural
n
um
b
ers
a
and
b
v
erifying
:
318
≡
a
(
mo
d.
9)
;
1
203
631
≡
b
(
mo
d.
9)
b
Using
the
conserv
ation
prop
erties
of
congruence,
sho
w
that
the
calculation
b
elo
w
is
false
:
3
785
×
318
=
1
203
631
E.23
The
aim
of
the
exercise
is
to
pro
v
e,
for
four-digit
in
tegers,
the
divisibilit
y
criterion
:
ˇAn
in
teger
is
divisible
b
y
3
if
and
only
if
the
sum
of
its
digits
is
itself
divisible
b
y
3ı.
1
An
example
:
a
F
or
a
natural
n
um
b
er
n
,
what
do
es
the
sen
tence
ˇ
me
an
n
is
c
ongruent
to
1
mo
dulo
3
ı?
T
ranslate
using
a
congruence
ˇ
n
is
divisible
b
y
3ı.
b
F
or
eac
h
of
the
follo
wing
in
tegers,
giv
e
the
smallest
p
ositiv
e
in
teger
to
whic
h
it
is
congruen
t
mo
dulo
3
:
10
,
100
,
1000
,
10
p
where
is
a
p
ositiv
e
in
teger.
c
Determine
the
smallest,
p
ositiv
e
in
teger
to
whic
h
is
congruen
t
the
in
teger
4520
mo
dulo
3
.
Note
that
:
4520
=
4
×
1000
+
5
×
100
+
2
×
10
.
2
Some
generalizations
:
Consider
a
four-digit
in
teger
N
,
four
in
tegers
a
,
b
,
c
and
d
b
et
w
een
0
and
9
suc
h
that
a
=
0
and
:
N
=
1000
·
a
+
100
·
b
+
10
·
c
+
d
.
The
units
are
d
,
the
tens
are
c
,
the
h
undreds
b
and
the
thousands
a
.
a
Sho
w
that
:
N
≡
a
+
b
+
c
+
d
mo
dulo
3.
b
Justify
,
for
four-digit
in
tegers,
the
criterion
of
divisibil-
it
y
b
y
3,
stated
at
the
b
eginning
of
the
exercise.
c
State
an
analogous
criterion
for
divisibilit
y
b
y
9
and
demonstrate
it
for
four-digit
in
tegers.
h
ttps:/
/c
hingmath.fr
chapExoCorrec/24
sacados/24
Liban - 2003 - 6 points - aux choix
chapExoCorrec/20
sacados/20
chapExoCorrec/27
sacados/27
sacados/23
France - Juin 2004 - 7 points - Au choix
E.1851
The
13-digit
barco
de,
or
EAN-13
(Eur
op
e
an
A
rticle
Numb
er)
,
is
a
co
de
consisting
of
13
digits
ranging
from
0
to
9,
used
to
classify
pro
ducts
in
mass
retail
:
a
1
a
2
a
3
a
4
a
5
a
6
a
7
a
8
a
9
a
10
a
11
a
12
a
13
The
calculation
is
as
follo
ws
:
S
=
a
1
+
3
a
2
+
a
3
+
3
a
4
+
a
5
+
3
a
6
+
a
7
+
3
a
8
+
a
9
+3
a
10
+
a
11
+
3
a
12
+
a
13
The
co
de
is
accepted
when
:
S
≡
0
(
mo
d.
10)
.
Otherwise,
it
is
rejected.
1
In
practice.
Consider
the
co
de
A
=
9
780
130
515
186
.
a
V
erify
that
A
is
accepted.
b
Instead
of
the
co
de
A
,
the
co
de
B
=
9
770
130
515
186
w
as
en
tered
with
an
error
in
the
third
digit.
Sho
w
that
the
co
de
B
is
rejected.
c
When
en
tering
the
co
de
A
,
t
w
o
adjacen
t
digits
w
ere
sw
app
ed.
Is
the
co
de
C
=
9
780
135
015
186
accepted
or
rejected?
Is
the
co
de
D
=
9
780
130
155
186
accepted
or
rejected?
2
Effect
of
an
en
try
error
on
the
fourth
digit.
a
Let
E
denote
the
co
de
9
78
n
130
515
186
,
where
n
rep-
resen
ts
a
digit.
If
n
=
0
,
w
e
obtain
the
co
de
A
,
so
E
is
accepted.
Determine
all
v
alues
of
n
for
whic
h
E
is
accepted.
b
Conclude
that
an
input
error
in
the
fourth
digit
of
the
co
de
A
is
alw
a
ys
detected.
E.11
D
A
VID’s
famous
pain
ting
:
ˇLe
sacre
de
Nap
oléonı
immortalizes
the
ev
en
t
of
Decem
b
er
2,
1804.
Ov
er
the
p
erio
d
under
consideration,
all
y
ears
with
vin
tages
in
m
ultiples
of
4
are
leap
y
ears,
with
the
exception
of
1900.
L
et’s
c
onsider
De
c
emb
er
2,
1804
as
the
day
of
r
ank
1
1
a
Ho
w
man
y
y
ears
ha
v
e
vin
tages
b
et
w
een
1805
(inclu-
sive)
and
2003
(inclusive)
?
b
Among
these
y
ears,
sho
w
that
there
are
48
leap
y
ears
2
Pro
v
e
that
the
rank
of
1
er
Jan
uary
2004
is
72
714
.
3
Determine
the
in
teger
a
b
et
w
een
0
and
6
inclusiv
e
suc
h
that
:
72
714
=
a
(
mo
d.
7)
.
4
Kno
wing
that
1
er
Jan
uary
2004
w
as
a
Th
ursda
y
,
cop
y
and
complete
the
follo
wing
table
where
k
denotes
an
in
teger.
Rang
du
jour
7
k
7
k
+1
7
k
+2
7
k
+3
7
k
+4
7
k
+5
7
k
+6
Jour
from
la
semaine
5
On
what
da
y
of
the
w
eek
w
as
Nap
oleon
1
er
cro
wned
em-
p
eror?
E.19
Questions
1
and
2
are
indep
en-
den
t.
1
Consider
t
w
o
natural
n
um
b
ers
a
and
b
suc
h
that
:
a
is
congruen
t
to
10
mo
dulo
23
b
is
congruen
t
to
15
mo
dulo
23
a
Determine
the
smallest
natural
in
teger
congruen
t
to
(
a
+
b
)
mo
dulo
23.
b
Determine
the
smallest
natural
in
teger
congruen
t
to
a
·
b
mo
dulo
23.
2
a
Determine
the
smallest
natural
n
um
b
er
congruen
t
to
1000
mo
dulo
111
b
Sho
w
that
for
an
y
natural
n
um
b
er
n
,
1000
n
is
congru-
en
t
to
n
mo
dulo
111.
Deduce
that
the
n
um
b
er
10
8
+10
4
+1
is
divisible
b
y
111.
E.2
new
Caledonia
-
6
p
oin
ts
-
No
v
em
b
er
2005
An
electronic
clo
c
k
has
b
een
programmed
to
b
eep
ev-
ery
sev
en
hours.
The
first
b
eep
is
emitted
at
midnigh
t
on
Decem
b
er
31.
1
a
A
t
what
time
is
the
last
b
eep
of
1
er
Jan
uary
2005?
b
What
time
is
the
first
b
eep
of
Jan
uary
2,
2005?
c
What
time
is
the
last
b
eep
of
Jan
uary
2,
2005?
d
What
time
is
the
first
b
eep
of
Jan
uary
3,
2005?
Explain
the
answ
ers.
2
a
Sho
w
that
:
24
≡
3
(
mo
d.
7)
b
Deduce
the
remainder
of
the
Euclidean
division
of
2
×
24
b
y
7
and
the
remainder
of
the
Euclidean
divi-
sion
of
3
×
24
b
y
7.
Justify
answ
ers.
Repro
duce
on
the
cop
y
and
complete
the
follo
wing
table
:
n
1
2
3
4
5
6
7
8
9
10
Reste
de
la
division
euclidienne
de
n
×
24
par
7
5
1
4
0
3
6
2
c
Explain
wh
y
the
clo
c
k
b
eeps
at
midnigh
t
ev
ery
7
da
ys
and
ev
ery
7
da
ys
only
.
3
Recall
that
2005
is
a
non-leap
y
ear
and
has
365
da
ys.
a
Determine
the
smallest
natural
n
um
b
er
a
suc
h
that
:
365
≡
a
(
mo
d.
7)
.
b
On
what
date
will
the
clo
c
k
b
eep
at
midnigh
t
for
the
last
time
in
2005?
Explain
the
answ
er.
h
ttps:/
/c
hingmath.fr
chapExoCorrec/1851
sacados/1851
chapExoCorrec/11
sacados/11
Antilles - 2004 - Au choix - 6 points
chapExoCorrec/19
sacados/19
Japon - 2002 - 5 point - au choix
sacados/2
E.18
In
this
exer
cise,
we
examine
divis-
ibility
by
11
by
using
the
c
ongruenc
e
mo
dulo
11
of
p
owers
of
10.
1
a
V
erify
that
:
100
≡
1
(
mo
d.
11)
.
Conclude
that
:
10
4
≡
1
(
mo
d.
11)
b
V
erify
that
:
10
≡
−
1
(
mo
d.
11)
.
Conclude
that
:
10
3
≡
−
1
(
mo
d.
11)
10
5
≡
−
1
(
mo
d.
11)
2
a
Using
the
equalit
y
3729
=
37
×
100+29
and
the
previ-
ous
results,
sho
w
that
3729
is
divisible
b
y
11.
b
Using
the
previous
metho
d,
in
v
estigate
the
divisibilit
y
of
9
240
b
y
11
.
3
a
Using
the
equalit
y
:
3729
=
3
×
1000
+
7
×
100
+
2
×
10
+
9
and
the
previous
results,
sho
w
that
3
729
is
divisible
b
y
11
.
b
Using
this
metho
d,
determine
whether
9
240
is
divisi-
ble
b
y
11
.
4
Determine
whether
197
277
is
divisible
b
y
11.
E.10
1
Giv
e
the
remainder
of
the
Euclidean
division
of
5
b
y
8.
Giv
e
the
remainder
of
the
Euclidean
division
of
5
2
b
y
8.
2
Giv
e
the
remainder
of
the
Euclidean
division
of
5
86
b
y
8.
Giv
e
the
remainder
of
the
Euclidean
division
of
5
87
b
y
8.
3
Giv
e
is
the
remainder
of
the
Euclidean
division
of
965
87
b
y
8.
4
Let
n
b
e
a
natural
n
um
b
er.
Sho
w
that
5
2
n
+1
+5
2
n
+2
is
a
m
ultiple
of
8.
E.1
The
iden
tification
co
de
for
an
item
consists
of
sev
en
digits
b
et
w
een
0
and
9.
The
first
six
digits
iden
tify
the
item,
and
the
sev
en
th
is
a
c
hec
k
digit
used
to
detect
errors
in
the
first
six
digits.
Suc
h
a
co
de
is
written
as
x
1
x
2
x
3
x
4
x
5
x
6
x
7
.
The
c
hec
k
digit
x
7
is
the
remainder
of
the
Euclidean
division
b
y
10
of
the
sum
:
N
=
(
x
1
+
x
3
+
x
5
)+7(
x
2
+
x
4
+
x
6
)
1
a
Chec
k
that
the
follo
wing
co
de
is
correct
:
2
3
4
1
5
4
7
b
Calculate
the
k
ey
for
the
follo
wing
co
de
:
9
2
3
4
5
1
•
c
One
of
the
digits
in
the
follo
wing
co
de
has
b
een
erased
:
1
1
2
•
7
7
4
.
Calculate
it.
2
In
this
question,
one
of
the
digits
in
the
co
de
is
incorrect
:
instead
of
en
tering
x
1
x
2
x
3
x
4
x
5
x
6
x
7
,
the
t
ypist
t
yp
ed
x
1
x
2
x
3
y
x
5
x
6
x
7
a
W
rite
the
sums
N
1
and
N
2
asso
ciated
with
the
t
w
o
pre-
vious
co
des
resp
ectiv
ely
,
then
calculate
the
difference
N
1
−
N
2
b
Sho
w
that
the
equation
7
a
=
0
(
mo
d.
10)
where
a
is
an
in
teger
b
et
w
een
0
and
9,
has
only
one
solution,
0.
c
Will
the
t
yping
error
b
e
detected?
3
In
this
question,
t
w
o
of
the
digits
in
the
co
de
ha
v
e
b
een
sw
app
ed
:
instead
of
t
yping
x
1
x
2
x
3
x
4
x
5
x
6
x
7
,
the
t
ypist
t
yp
ed
x
1
x
3
x
2
x
4
x
5
x
6
x
7
.
a
W
rite
the
sums
N
1
and
N
2
asso
ciated
with
these
t
w
o
co
des,
then
calculate
the
difference
N
1
−
N
2
.
b
Giv
e
an
example
of
v
alues
for
x
2
and
x
3
for
whic
h
the
c
hec
k
digit
do
es
not
detect
the
error.
h
ttps:/
/c
hingmath.fr
chapExoCorrec/18
sacados/18
Japon -- 2003 -- au choix -- 5 points
chapExoCorrec/10
sacados/10
Liban -- 2005 - 6 points -- au choix
chapExoCorrec/1
sacados/1
Japon - 2004 - 6 points - au choix
E.25
A
le
ap
ye
ar
has
366
days,
and
a
non-le
ap
ye
ar
has
365
days.
A
ye
ar
is
a
le
ap
ye
ar
if
its
ˇnum-
b
erı
is
divisible
by
4,
unless
it
is
a
c
entury
ye
ar.
Century
ye
ars≠ye
ars
whose
ˇnumb
erı
ends
in
two
zer
os≠ar
e
gener
al
ly
not
le
ap
ye
ars
unless
their
ˇnumb
erı
is
divisible
by
400.
Some
examples
:
1996
was
a
le
ap
ye
ar,
1997
was
not,
nor
was
1900,
but
2400
wil
l
b
e.
1
Find
the
t
w
o
natural
n
um
b
ers
a
and
b
less
than
or
equal
to
6
suc
h
that
:
365
≡
a
(
mo
d.
7)
;
366
≡
b
(
mo
d.
7)
.
2
a
Assuming
that
Jan
uary
1
of
a
non-leap
y
ear
falls
on
a
Monda
y
,
explain
wh
y
Jan
uary
1
of
the
follo
wing
y
ear
will
fall
on
a
T
uesda
y
.
b
If
Jan
uary
1
of
a
leap
y
ear
falls
on
a
Monda
y
,
what
da
y
of
the
w
eek
will
Jan
uary
1
of
the
follo
wing
y
ear
fall
on?
3
A
p
erio
d
of
four
consecutiv
e
y
ears
has
:
N
=
3
×
365
+
1
×
366
.
Without
calculating
N
,
justify
that
N
≡
5
(
mo
d.
7)
.
4
Assuming
that
Jan
uary
1
of
a
giv
en
y
ear
is
a
Monda
y
,
what
da
y
of
the
w
eek
will
Jan
uary
1
b
e
four
y
ears
later?
Explain
y
our
answ
er.
Mor
e
gener
al
ly,
for
a
given
date,
(for
example,
1
st
Jan-
uary)
,
e
ach
4-ye
ar
p
erio
d
r
esults
in
a
five-day
shift
in
the
cycle
of
the
days
of
the
we
ek
5
Complete
the
table
b
elo
w.
No
explanation
is
required.
Num
b
er
of
four-y
ear
p
erio
ds
J
=
n
um
b
er
of
da
ys
of
shift
in
the
cycle
of
the
da
ys
of
the
w
eek
Remainder
of
the
division
of
J
b
y
7
0
0
0
1
5
5
2
10
3
3
4
5
6
7
6
a
Explain
wh
y
2004
is
a
leap
y
ear.
b
Giv
en
that
F
ebruary
29,
2004,
w
as
a
Sunda
y
,
what
da
y
of
the
w
eek
will
F
ebruary
29,
2008,
b
e?
c
When
will
the
next
y
ear
b
e
in
whic
h
F
ebruary
29
falls
on
a
Sunda
y?
Explain
y
our
answ
er.
E.1770
A
natural
n
um
b
er
N
is
written
cabc
in
e
base-fiv
e
n
umeration
system
where
a
,
b
,
c
are
non-zero,
i.e.
:
N
=
c
×
5
3
+
a
×
5
2
+
b
×
5
+
c
where
a
,
b
,
c
are
in
tegers
suc
h
that
:
0
<
a
<
5
;
0
<
b
<
5
;
0
<
c
<
5
This
same
in
teger
N
is
written
aba
in
the
base-eigh
t
n
um
b
er-
ing
system.
1
Sho
w
that
N
=
65
·
a
+8
·
b
and
deduce
that
:
40
·
a
=
126
·
c
−
3
b
·
.
2
a
Justify
that
40
·
a
≡
0
(
mo
d.
3)
.
Deduce
the
v
alue
of
a
.
b
Sho
w
that
b
≡
0
(
mo
d.
2)
.
Determine
the
v
alues
of
b
and
c
.
c
Giv
e
the
writing
of
the
in
teger
N
in
bases
fiv
e,
eigh
t
and
ten.
E.1989
The
aim
of
this
exercise
is
to
sho
w,
b
y
t
w
o
differen
t
metho
ds,
that
for
an
y
natural
n
um
b
er
n
,
the
n
um
b
er
n
3
+5
·
n
is
divisible
b
y
6.
First
metho
d
1
Sho
w
that
an
y
natural
n
um
b
er
n
is
congruen
t,
mo
dulo
6,
to
0,
1,
2,
3,
4
or
5.
2
Cop
y
and
complete
the
follo
wing
table
with
natural
n
um-
b
ers
less
than
or
equal
to
5.
n
≡
:
:
:
(
mo
d.
6)
0
1
2
3
4
5
n
3
≡
:
:
:
(
mo
d.
6)
5
n
≡
:
:
:
(
mo
d.
6)
n
3
+
5
n
≡
:
:
:
(
mo
d.
6)
3
Deduce
that
for
an
y
natural
in
teger
n
,
the
in
teger
n
3
+5
n
is
divisible
b
y
6.
Second
metho
d
1
Sho
w
that
for
an
y
natural
n
um
b
er
n
:
n
·
(
n
+
1)
is
ev
en.
Deduce
that
for
an
y
natural
n
um
b
er
n
:
3
·
n
·
(
n
+
1)
is
divisible
b
y
6.
2
W
e
admit
that
:
(
n
+
1)
3
+
5
·
(
n
+
1)
=
(
n
3
+
5
·
n
)
+
3
·
n
·
(
n
+
1)
+
6
Sho
w
that
if
for
a
natural
n
um
b
er
;
n
3
+5
·
n
is
divisible
b
y
6,
then
(
n
+1)
3
+5
·
(
n
+1)
is
divisible
b
y
6.
3
What
remains
to
c
hec
k,
to
deduce
that
n
3
+5
·
n
is
divisi-
ble
b
y
6,
for
an
y
natural
n
um
b
er
n
?
2.
Congruenc
e
and
p
ower
E.1849
1
a
Determine
the
remainders
when
the
in
tegers
3
n
are
divided
b
y
7
using
the
Euclidean
algorithm
for
n
∈
N
:
n
6
.
b
Cop
y
and
complete
the
follo
wing
table
:
P
o
w
er
of
3
3
0
3
1
3
2
3
3
3
4
3
5
3
6
Remainder
mo
dulo
7
c
Conclude
that,
for
an
y
k
∈
N
,
3
6
k
is
congruen
t
to
1
h
ttps:/
/c
hingmath.fr
chapExoCorrec/25
sacados/25
chapExoCorrec/1770
sacados/1770
sacados/1989
chapExoCorrec/1849
sacados/1849
mo
dulo
7.
2
a
Find
the
smallest
natural
n
um
b
er
congruen
t
to
1515
mo
dulo
7.
b
After
noting
that
2004
=
6
×
334
,
use
1
to
determine
the
remainder
of
the
Euclidean
division
of
1515
2004
b
y
7.
c
Sho
w
that
in
the
Euclidean
division
of
1515
2006
b
y
7,
the
remainder
is
2.
E.28
1
a
Sho
w
that
1999
is
congruen
t
to
4
mo
dulo
7.
b
Determine
the
smallest
natural
n
um
b
er
congruen
t
to
2007
mo
dulo
7.
2
Let
n
b
e
a
natural
n
um
b
er
congruen
t
to
5
mo
dulo
7.
a
Determine
a
natural
n
um
b
er
congruen
t
to
n
3
mo
dulo
7.
b
Deduce
that
(
n
3
+1)
is
divisible
b
y
7.
3
Sho
w
that
if
n
is
a
natural
n
um
b
er
congruen
t
to
4
mo
dulo
7
then
(
n
3
−
1)
is
divisible
b
y
7.
4
Consider
the
n
um
b
er
:
A
=
1999
3
+2007
3
.
Without
calculating
A
,
sho
w
using
the
previous
results
that
A
is
divisible
b
y
7.
E.7
Consider
the
in
tegers
:
A
=
8
387
592
115
;
B
=
9
276
312
516
1
a
Sho
w
that
1
000
is
divisible
b
y
8.
b
Sho
w
that
A
is
congruen
t
to
3
mo
dulo
8.
c
Find
the
natural
n
um
b
er
b
strictly
less
than
8
suc
h
that
B
is
congruen
t
to
b
mo
dulo
8.
2
Determine
the
natural
n
um
b
ers
strictly
less
than
8
that
are
congruen
t
to
A
+
B
and
A
·
B
,
resp
ectiv
ely
,
mo
dulo
8
.
3
a
Sho
w
that
B
2
is
divisible
b
y
8.
b
Sho
w
that
A
2
is
not
divisible
b
y
8.
c
Sho
w
that
A
100
is
not
divisible
b
y
8.
E.8
Consider
the
in
teger
A
=
18
2002
.
1
A
Is
it
divisible
b
y
9?
By
4?
(Justify
your
answers.)
2
W
e
w
an
t
to
find
the
remainder
of
the
Euclidean
division
of
A
b
y
7,
using
congruences.
a
Find
the
in
teger
r
suc
h
that
:
0
r
<
7
18
=
r
(
mo
d.
7)
b
What
is
the
smallest
nonzero
natural
n
um
b
er
n
suc
h
that
:
r
n
=
1
(
mo
d.
7)
?
c
Pro
v
e
that
for
an
y
natural
n
um
b
er
k
,
4
3
k
is
congruen
t
to
1
mo
dulo
7.
d
Deduce
the
remainder
of
the
Euclidean
division
of
A
b
y
7.
3
Sho
w
that
2002
18
is
divisible
b
y
13.
E.1769
F
or
an
y
in
teger
n
1
,
consider
the
in
teger
:
11
n
+
5
n
−
7
1
a
What
is
the
remainder
of
11
in
Euclidean
division
b
y
10?
b
Sho
w
that,
for
an
y
in
teger
n
1
:
11
n
≡
1
(
mo
d.
10)
.
2
Demonstrate
that,
for
an
y
in
teger
n
1
,
5
n
≡
5
(
mo
d.
10)
.
(W
e
c
an
use
r
e
asoning
by
r
e
curr
enc
e
or
r
ely
on
divisibility
pr
op
erties)
3
What
is
the
units
digit
of
the
in
teger
11
2007
+
5
2007
−
7
?
Justify
the
answ
er
giv
en.
E.1848
1
Sho
w
that,
for
an
y
n
∈
N
,
w
e
ha
v
e
:
2
3(
n
+1)
−
1
=
8
·
2
3
n
−
1
+
7
.
2
Sho
w,
using
reasoning
b
y
recurrence,
that
the
follo
wing
prop
ert
y
is
true
for
an
y
n
∈
N
:
2
3
n
−
1
is
divisible
b
y
7.
E.35
1
Sho
w
the
follo
wing
relationship
for
n
∈
N
:
9
·
9
n
−
2
n
+
7
×
2
n
2
Sho
w
b
y
recurrence
that
9
n
−
2
n
is
a
m
ultiple
of
7
for
an
y
n
∈
N
.
3.
V
erific
ation
key
pr
oblem
E.15
On
the
catalog
of
a
mail-order
com-
pan
y
,
the
reference
of
eac
h
item
of
a
fiv
e-digit
n
um
b
er
x
y
z
t
u
(the
first
of
these
numb
ers
x
b
eing
non-zer
o)
,
follo
w
ed
b
y
a
capital
letter
c
hosen
b
et
w
een
A
and
N
,
with
the
exception
of
the
letter
I
.
This
upp
ercase
letter
is
asso
ciated
with
a
n
um
b
er
called
the
k
ey
,
according
to
the
follo
wing
table
:
Lettre
A
B
C
D
E
F
G
H
J
K
L
M
N
Clé
0
1
2
3
4
5
6
7
8
9
10
11
12
F
or
con
trol
purp
oses,
for
eac
h
reference,
the
sum
of
the
fiv
e-
digit
n
um
b
er
and
the
k
ey
obtained
from
the
table
m
ust
b
e
a
n
um
b
er
divisible
b
y
13.
F
or
example,
let’s
consider
an
item
whose
reference
is
18
501M.
The
fiv
e-digit
n
um
b
er
is
18
501
.
The
k
ey
asso
ciated
with
M
is
11
:
18501
+
11
=
18512
=
13
×
1424
.
18512
is
divisible
b
y
13,
so
this
reference
is
correct.
1
Are
the
follo
wing
t
w
o
part
n
um
b
ers
correct?
13587
M
;
45905
A
Answ
ers
m
ust
b
e
justified.
2
W
e
w
an
t
to
find
the
letter
of
a
reference
of
whic
h
only
the
fiv
e-digit
n
um
b
er
26014
remains.
a
Sho
w
that
:
13
×
2001
<
26014
<
13
×
2002
.
b
Deduce
the
missing
letter.
h
ttps:/
/c
hingmath.fr
sacados/28
Antilles Guyane - Juin 2002 - 5 points
chapExoCorrec/7
sacados/7
Antilles - Septembre 2002 - 7 points - au choix
chapExoCorrec/8
sacados/8
Liban - Juin 2002 - 6 points
sacados/1769
chapExoCorrec/1848
sacados/1848
sacados/35
sacados/15
3
W
e
w
an
t
to
find
an
illegible
n
um
b
er
in
the
reference
of
an
article.
This
reference
is
85
z
29
C
(
z
b
eing
the
il
le
gible
digit)
.
a
Sho
w
that
the
problem
b
oils
do
wn
to
finding
z
suc
h
that
0
z
9
and
:
8
×
10
4
+5
×
10
3
+
z
×
10
2
+2
×
10+9+2
≡
0
(
mo
d.
13)
This
relationship
will
b
e
noted
(
E
)
throughout
the
se-
quel.
b
Cop
y
and
complete
the
follo
wing
table
using
natural
n
um
b
ers
b
et
w
een
0
and
12.
10
0
≡
:
:
:
(
mo
d.
13)
10
1
≡
:
:
:
(
mo
d.
13)
10
2
≡
:
:
:
(
mo
d.
13)
10
3
≡
:
:
:
(
mo
d.
13)
10
4
≡
:
:
:
(
mo
d.
13)
c
Using
the
prop
erties
of
congruences
and
the
results
obtained
in
the
previous
table,
sho
w
that
the
problem
amoun
ts
to
finding
z
(
0
z
9
)
suc
h
that
:
11
+
9
z
≡
(
mo
d.
13)
d
Determine
the
unreadable
digit
of
the
reference.
Then
write
this
reference.
E.9
In
a
mail-order
compan
y
,
item
n
um-
b
ers
are
made
up
of
6
digits
and
a
c
hec
k
letter
to
a
v
oid
input
errors.
The
p
osition
of
the
letter
in
the
alphab
et
corresp
onds
to
the
remainder
of
the
n
umerical
reference
divided
b
y
26.
Example
:
the
n
umerical
reference
123
456
=
4748
×
26+8
and
the
8
e
letter
of
the
alphab
et
is
H
so
the
item
reference
with
its
con
trol
k
ey
is
123
456
H
.
1
The
n
umerical
reference
of
an
item
is
784
503
,
determine
the
con
trol
letter
corresp
onding
to
this
reference.
2
Consider
the
reference
:
:
:
37
254
H
where
the
first
digit
has
b
een
deleted.
a
W
e
note
n
the
missing
digit
;
V
erify
that
the
n
um
b
er
v
erifies
:
n
·
37
254
=
n
×
100
000
+
37
254
b
Determine
the
remainder
of
dividing
100
000
b
y
26,
then
37
254
b
y
26.
c
Deduce
that
:
4
·
n
+22
=
8
(
mo
d.
26)
.
d
Kno
wing
that
1
n
9
,
determine
the
missing
digit
of
the
reference.
E.3
The
I.N.S.E.E.
n
um
b
er
is
made
up
of
15
digits.
Reading
from
left
to
righ
t
:
The
first
n
um
b
er
is
1
if
male,
2
if
female
;
the
next
t
w
o
digits
designate
the
last
t
w
o
digits
of
the
y
ear
of
birth
;
the
follo
wing
t
w
o
digits
designate
the
mon
th
of
birth
;
the
next
t
w
o
digits
designate
the
departmen
t
of
birth
;
the
next
three
digits
designate
the
comm
une
of
birth
;
the
next
three
digits
designate
the
civil
registration
n
um-
b
er
;
the
last
t
w
o
digits
designate
the
k
ey
K
,
calculated
as
follo
ws
:
Let
A
b
e
the
in
teger
made
up
of
the
13
digits
on
the
left,
b
e
r
the
remainder
of
the
Euclidean
division
of
A
b
y
97,
then
K
=
97
−
r
The
first
13
digits
(without
key)
of
Sophie’s
n
um
b
er
I
.
N
.
S
.
E
.
E
.
are
2
850
786
183
048
.
W
e
denote
A
this
n
um
b
er
and
r
the
remainder
of
the
Euclidean
division
of
A
b
y
97.
1
Giv
e
the
mon
th
of
Sophie’s
birth
y
ear.
2
a
Determine
the
t
w
o
in
tegers
a
and
b
suc
h
that
:
A
=
a
×
10
6
+
b
with
0
b
<
10
6
.
b
Using
the
remainder
of
100
in
its
Euclidean
division
b
y
97
;
sho
w
that
:
10
6
≡
27
(
mo
d.
97)
c
Deduce
the
remainder
r
of
the
Euclidean
division
of
A
b
y
97.
3
Determine
the
k
ey
K
of
Sophie’s
I.N.S.E.E.
n
um
b
er.
4
Sophie,
ask
ed
for
the
first
thirteen
digits
of
her
I.N.S.E.E.
n
um
b
er,
rev
erses
the
last
t
w
o
digits
and
an-
sw
ers
2
850
786
183
084
instead
of
2
850
786
183
048
.
W
e
note
B
Sophie’s
answ
er.
a
Calculate
the
difference
B
−
A
and
deduce
that
the
re-
mainder
of
the
Euclidean
division
of
B
b
y
97
is
equal
to
21.
b
Can
the
error
made
b
y
Sophie
b
e
detected?
E.1850
All
published
w
orks
are
iden
tified
b
y
an
ISBN
n
um
b
er
(International
Standar
d
Bo
ok
Numb
er)
whic
h
indicates
the
language
of
publication,
the
publisher
and
the
reference
of
the
w
ork
with
that
publisher.
An
ISBN
n
um-
b
er
consists
of
nine
digits
(i.e.
nine
inte
gers
b
etwe
en
0
and
9)
follo
w
ed
b
y
a
space
and
a
k
ey
.
This
k
ey
is
a
digit
or
the
letter
X
(the
10
in
R
oman
numb
ering)
.
T
o
determine
the
k
ey
of
an
ISBN
n
um
b
er
whose
first
nine
digits
are
abcdef
g
hi
,
w
e
calculate
the
in
teger
:
N
=
a
+2
·
b
+3
·
c
+4
·
d
+5
·
e
+6
f
·
+7
·
g
+8
·
h
+9
·
i
then
determine
the
in
teger
r
b
et
w
een
0
and
10
that
is
congru-
en
t
to
N
mo
dulo
11
.
If
the
in
teger
r
is
strictly
less
than
10
,
the
k
ey
is
equal
to
r
;
if
the
in
teger
r
is
equal
to
10
,
the
k
ey
is
X
.
1
Chec
k
that
the
ISBN
n
um
b
er
k
ey
190190340
0
is
correct.
2
Calculate
the
k
ey
for
the
ISBN
n
um
b
er
whose
first
9
dig-
its
are
:
103
241
052.
3
The
fourth
digit
of
a
b
o
ok’s
ISBN
n
um
b
er
is
illegible.
It
is
noted
as
d
.
The
k
ey
for
this
n
um
b
er
is
4
and
the
n
um
b
er
lo
oks
lik
e
this
:
329
D12
560
4
a
Sho
w
that
:
4
·
d
≡
2
(
mo
d.
11)
.
b
Deduce
the
n
um
b
er
d
.
4
The
first
and
nin
th
digits
of
a
b
o
ok’s
ISBN
n
um
b
er
are
illegible.
They
are
noted
as
a
and
i
.
The
k
ey
for
this
n
um
b
er
is
9
and
the
n
um
b
er
lo
oks
lik
e
this
:
a32
100
50i.
a
Sho
w
that
:
a
≡
2
−
9
·
i
(
mo
d.
11)
.
b
Giv
e
t
w
o
p
ossible
v
alues
of
the
pair
(
a
;
i
)
.
h
ttps:/
/c
hingmath.fr
chapExoCorrec/9
sacados/9
chapExoCorrec/3
sacados/3
Antilles - 2003 - 7 points - Obligatoire
chapExoCorrec/1850
sacados/1850
4.
Co
ding
E.21
Bank
card
PINs
are
made
up
of
four
digits
from
0
to
9.
Pierre
didn’t
write
do
wn
his
bank
card’s
co
de
in
his
diary
,
but
as
he’s
afraid
of
forgetting
it,
he
wrote
do
wn
the
ˇ
encrypte
d
form
ı
of
his
secret
co
de
so
that
his
secret
co
de
w
ould
not
b
e
disco
v
ered
if
his
diary
w
ere
lost.
Pierre
alw
a
ys
p
erforms
his
encryption
as
follo
ws
:
He
c
ho
oses
t
w
o
n
um
b
ers
a
and
b
,
called
ˇ
cryptage
ı
k
eys,
whic
h
he
will
use
for
all
the
encryption.
He
replaces
eac
h
digit
n
of
his
secret
co
de
with
the
digit
p
,
called
the
encrypted
form
of
n
,
whic
h
he
calculates
using
the
follo
wing
form
ula
:
p
≡
a
×
n
+
b
(
mo
d.
10)
The
aim
of
part
A
is
to
find
the
secret
co
de
of
Pierre’s
bank
card,
kno
wing
the
encryption
k
eys.
The
ob
jectiv
e
of
part
B
is
to
find
the
encryption
k
eys.
The
parts
A
and
B
are
therefore
indep
enden
t.
P
art
A
Pierre
has
c
hosen
here
:
a
=
3
;
b
=
7
Then
:
p
≡
3
×
n
+
7
(
mo
d.
10)
F
or
example,
the
encrypted
form
of
the
n
um
b
er
5
will
b
e
the
n
um
b
er
2.
Because
:
3
×
5
+
7
=
22
;
22
≡
2
(
mo
d.
10)
1
Repro
duce
and
complete
the
encryption
table
b
elo
w
cor-
resp
onding
to
Pierre’s
form
ula.
n
0
1
2
3
4
5
6
7
8
9
p
6
9
2
1
2
Pierre
has
written
8
5
0
3
in
his
diary
whic
h
is
the
en-
crypted
form
of
his
secret
co
de,
what
is
his
real
secret
co
de?
P
art
B
Pierre
has
made
em
ulators.
Quen
tin
uses
the
same
form
ula
as
Pierre
:
p
≡
a
×
n
+
b
(
mo
d.
10)
But
b
y
taking
t
w
o
other
v
alues
of
a
and
b
from
the
n
um
b
ers
0
to
9.
Pierre
claims
to
b
e
able
to
determine
Quen
tin’s
form
ula
(i.e.
find
the
numb
ers
a
and
b
)
,
as
the
latter
has
confessed
to
him
the
encrypted
forms
of
t
w
o
n
um
b
ers
:
The
encrypted
form
of
the
n
um
b
er
3
is
the
n
um
b
er
3
.
The
encrypted
form
of
the
digit
4
is
the
digit
2
.
1
Establish
that
disco
v
ering
a
and
b
amoun
ts
to
solving
the
system
of
unkno
wn
(
a
;
b
)
:
3
a
+
b
≡
3
(
mo
d.
10)
4
a
+
b
≡
2
(
mo
d.
10)
where
a
and
b
are
n
um
b
ers
from
0
to
9.
2
Pierre
claims
that
the
couple
(
9
;
6
)
is
a
solution
of
this
system.
Sho
w
that
he
is
righ
t
E.17
P
arts
I
and
I
I
are
indep
enden
t.
P
art
I
Nathalie
comm
unicates
with
a
friend
b
y
making
co
ded
mes-
sages.
Eac
h
letter
of
the
alphab
et
is
mark
ed
b
y
its
rank
x
,
1
x
26
:
1
for
A
,
2
for
B
,
etc.
.
.
The
rank
letter
x
is
enco
ded
b
y
the
rank
letter
y
suc
h
that
:
1
y
26
;
y
≡
x
+
10
(
mo
d.
26)
Examples
:
The
letter
V
has
r
ank
x
=
22
;
we
have
:
1
y
26
;
y
≡
32
(
mo
d.
26)
so
y
=
6
.
The
letter
V
is
enc
o
de
d
by
the
letter
F
.
1
Cop
y
and
dra
w
up
the
table
b
elo
w
for
all
the
letters
of
the
alphab
et.
Lettre
A
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
V
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
x
1
22
y
11
6
Co
ding
K
F
2
Find
the
co
ding
of
the
w
ord
ˇ
ARITHMETIQUE
ı.
3
Deco
de
the
w
ord
ˇ
OEBY
ı.
P
art
I
I
1
Noting
that
999
=
27
×
37
,
demonstrate
that
:
10
3
≡
1
(
mo
d.
37)
;
10
30
≡
1
(
mo
d.
37)
2
Demonstrate
that,
for
an
y
natural
n
um
b
er
n
,
w
e
ha
v
e
:
10
3
n
≡
1
(
mo
d.
37)
.
3
Deduce
that
the
in
teger
N
=
10
10
+10
20
+10
30
is
a
m
ulti-
ple
of
37.
(Note
that
10
10
=
10
9
×
10
)
.
h
ttps:/
/c
hingmath.fr
chapExoCorrec/21
sacados/21
chapExoCorrec/17
sacados/17
E.22
ˇ
The
c
onstant
b
attle
b
etwe
en
c
o
de
de-
signers
and
c
o
de
br
e
akers
has
le
d
to
a
series
of
r
emarkable
sci-
entific
br
e
akthr
oughs.
Designers
sought
to
develop
ever
mor
e
sophistic
ate
d
c
o
des
to
pr
ote
ct
c
ommunic
ations,
while
c
o
de-
br
e
akers
p
erp
etual
ly
devise
d
b
etter
metho
ds
of
attacking
them...
Their
work
ac
c
eler
ate
d
te
chnolo
gic
al
development,
p
articularly
in
the
c
ase
of
the
c
omputer....
The
art
of
se
cr
et
c
ommunic
ation,
also
known
as
crypto
gr
aphy,
would
pr
ovide
the
information
age
with
its
lo
cks
and
keys
ı.
History
of
Secret
Co
des
-
Simon
Singh
The
ASCI
I
co
de
(A
meric
an
Standar
d
Co
de
for
Informa-
tion
Inter
change)
in
computing,
allo
ws
eac
h
c
haracter
(letter,
punctuation
mark,
numb
er,.
.
.
)
to
b
e
asso
ciated
with
an
in-
teger
n
,
b
et
w
een
0
and
255.
The
table
b
elo
w
sho
ws
the
co
des
assigned
to
the
letters
of
the
alphab
et
:
Letter
A
B
C
D
E
F
G
H
I
J
K
L
M
ASCI
I
co
de
65
66
67
68
69
70
71
72
73
74
75
76
77
Letter
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
ASCI
I
co
de
78
79
80
81
82
83
84
85
86
87
88
89
90
1
ˇChiffremen
tı
k
ey
ed
using
arithmetic
The
follo
wing
pro
cedure
is
used
to
mask
the
initial
w
ord
:
to
eac
h
n
um
b
er
n
,
of
the
ASCI
I
Co
de
corresp
onding
to
a
giv
en
letter,
w
e
asso
ciate
the
remainder
of
the
division
of
7
n
b
y
256.
Example
:
Co
ding
of
the
letter
B
ASCI
I
co
de
of
letter
B
:
66.
Calculation
of
the
new
letter
co
de
B
:
7
×
66
=
462
;
462
=
256
×
1
+
206
.
New
letter
co
de
B
:
206
Th
us
the
w
ord
HELLO
will
b
e
co
ded
:
Mot
B
O
N
J
O
U
R
ASCI
I
co
de
66
79
78
74
79
85
82
New
co
ding
206
41
34
6
41
83
62
CLE
w
ord
co
ding
a
ASCI
I
co
de
for
C
:
67
;
7
×
67
=
469
Determine
the
remainder
of
the
Euclidean
division
of
469
b
y
256,
deduce
the
new
letter
co
de
C
.
b
In
the
same
w
a
y
,
determine
the
new
co
de
for
the
letter
L,
then
the
letter
E,
then
the
letter
F,
deducing
the
co
ding
for
the
w
ord
CLEF.
2
ˇDéc
hiffremen
tı
:
Let
x
b
e
the
new
co
de
of
the
letter
to
b
e
disco
v
ered
and
n
its
ASCI
I
co
de.
a
Justify
that
:
x
=
7
·
n
(
mo
d.
256)
b
Deduce
that
:
193
·
x
=
n
(
mo
d.
256)
.
Let
n
b
e
the
remainder
of
the
Euclidean
division
of
183
·
x
b
y
256.
c
Chec
k
that
for
x
=
206
,
w
e
ha
v
e
n
=
66
whic
h
corre-
sp
onds
to
the
letter
B
.
d
Deco
de
the
follo
wing
w
ord
:
206
199
213
E.4
Arth
ur
and
Wilson
are
t
wins
who
usually
comm
unicate
using
co
ded
messages.
They
alw
a
ys
encrypt
their
messages
as
follo
ws
:
Eac
h
letter
of
the
alphab
et
with
its
order
n
um
b
er
n
is
replaced
b
y
the
letter
of
the
alphab
et
with
order
n
um
b
er
p
(1
p
26)
obtained
using
the
form
ula
:
p
=
3
×
n
+
7
(
mo
d.
26)
F
or
example,
the
encrypted
form
of
L
is
Q
b
ecause
:
3
×
12+7
=
43
and
43
=
17
(
mo
d.
26)
.
1
Repro
duce
and
complete
the
encryption
table
b
elo
w
(no
justific
ation
r
e
quir
e
d)
.
lettre
A
B
C
D
E
F
G
H
I
J
K
L
M
N
n
1
2
3
4
5
6
7
8
9
10
11
12
13
14
p
17
forme
cryptée
J
Q
lettre
O
P
Q
R
S
T
U
V
W
X
Y
Z
n
15
16
17
18
19
20
21
22
23
24
25
26
p
1
forme
cryptée
A
2
Arth
ur
sen
t
the
follo
wing
message
to
Wilson
:
M
I
J
U
Z
C
Z
R
I
O
J
I
V
R
LLH
O
V
.
Find
the
decrypted
form
of
the
message.
3
Wilson
w
an
ts
to
reply
:
M
E
R
C
I
.
Giv
e
the
encrypted
form
of
this
message.
5.
Pr
op
erty
of
gc
d
and
cfcm
E.3865
Indicate
whether
the
follo
wing
statemen
t
is
true
or
false
and
pro
vide
a
pro
of
for
y
our
an-
sw
er.
ˇThere
is
only
one
pair
(
a
;
b
)
of
natural
n
um
b
ers
suc
h
that
:
a
<
b
;
P
P
C
M
(
a
;
b
)
−
P
GC
D
(
a
;
b
)
=
1
ı
E.3866
Indicate
whether
the
follo
wing
prop
osition
is
true
or
false
and
giv
e
a
demonstration
of
the
c
hosen
answ
er.
ˇW
e
consider
the
equation
:
(
E
)
:
x
2
−
52
x
+480
=
0
where
x
is
a
natural
n
um
b
er.
There
exist
t
w
o
non-zero
natural
n
um
b
ers
whose
P
GC
D
and
P
P
C
M
are
solutions
of
the
equation
(
E
)
.ı
h
ttps:/
/c
hingmath.fr
sacados/22
Liban - 2004 - 7 points - au choix
chapExoCorrec/4
sacados/4
chapExoCorrec/3865
sacados/3865
chapExoCorrec/3866
sacados/3866
Extrait Liban Juin 2010
E.4118
Let
U
n
b
e
the
n
umerical
sequence
defined
b
y
:
U
0
=
0
U
n
+1
=
2
·
U
n
+
1
p
our
tout
n
∈
N
1
Sho
w
that,
for
an
y
natural
n
um
b
er
n
,
U
n
+1
and
U
n
are
prime
to
eac
h
other.
2
Sho
w
that
for
an
y
natural
n
um
b
er
n
:
U
n
=
2
n
−
1
3
Sho
w
that,
for
all
non-zero
natural
n
um
b
ers
n
and
p
suc
h
that
n
p
:
U
n
=
U
p
·
U
n
−
p
+
1
+
U
n
−
p
The
notation
pgcd
(
a
;
b
)
is
used,
in
the
follo
wing,
to
designate
the
greatest
common
divisor
of
t
w
o
natural
n
um
b
ers
a
and
b
.
4
Sho
w
for
n
p
equalit
y
:
pgcd
(
U
n
;
U
p
)
=
pgcd
(
U
p
;
U
n
−
p
)
5
Let
n
and
p
b
e
t
w
o
non-zero
natural
n
um
b
ers,
sho
w
that
:
pgcd
(
U
n
;
U
p
)
=
U
pgcd
(
n
;
p
)
Determine
the
in
teger
:
pgcd
(
U
2005
;
U
15
)
.
6.
F
ermat’s
little
the
or
em
E.3192
The
aim
of
the
exercise
is
to
study
certain
divisibilit
y
prop
erties
of
the
in
teger
4
n
−
1
,
when
n
is
a
natural
n
um
b
er.
W
e
recall
the
prop
ert
y
kno
wn
as
F
ermat’s
little
theorem
:
ˇ
If
p
is
a
prime
in
teger
and
a
a
prime
natural
n
um
b
er
with
p
,
then
a
p
−
1
−
1
≡
0
(
mo
d.
p
)
ı
P
art
A.
Some
examples.
1
Demonstrate
that,
for
an
y
natural
n
um
b
er
n
,
4
n
is
con-
gruen
t
to
1
mo
dulo
3
.
2
Pro
v
e,
using
F
ermat’s
little
theorem,
that
4
28
−
1
is
divis-
ible
b
y
29
.
3
F
or
1
n
4
,
determine
the
remainder
of
the
division
of
4
n
b
y
17
.
Deduce
that,
for
an
y
in
teger
k
,
the
in
teger
4
4
k
−
1
is
divisible
b
y
17
.
4
F
or
whic
h
natural
in
tegers
n
is
the
in
teger
4
n
−
1
divisible
b
y
5?
5
Using
the
previous
questions,
determine
four
prime
divi-
sors
of
4
28
−
1
.
P
art
B.
Divisibilit
y
b
y
a
prime
in
teger
Let
p
b
e
a
prime
in
teger
other
than
2
.
1
Pro
v
e
that
there
exists
an
in
teger
n
1
suc
h
that
:
4
n
≡
1
(
mo
d.
p
)
.
2
Let
n
1
b
e
a
natural
n
um
b
er
suc
h
that
4
n
≡
1
(
mo
d.
p
)
.
Let
b
b
e
the
smallest
strictly
p
ositiv
e
in
teger
suc
h
that
4
b
≡
1
(
mo
d.
p
)
and
r
the
remainder
of
the
Euclidean
division
of
n
b
y
b
:
a
Pro
v
e
that
4
r
≡
1
(
mo
d.
p
)
.
Deduce
that
r
=
0
.
b
Pro
v
e
the
equiv
alence
:
4
n
−
1
is
divisible
b
y
p
if,
and
only
if,
n
is
a
m
ultiple
of
b
.
c
Deduce
that
b
divides
p
−
1
.
E.4275
Recall
the
prop
ert
y
kno
wn
as
F
er-
mat’s
little
theorem
:
ˇ
If
p
is
a
prime
in
teger
and
q
a
prime
natural
n
um
b
er
with
p
,
then
q
p
−
1
≡
1
(
mo
d.
p
)
.
ı
Consider
the
sequence
u
n
defined
for
an
y
non-zero
natural
n
um
b
er
n
b
y
:
u
n
=
2
n
+
3
n
+
6
n
−
1
Let
p
b
e
a
prime
in
teger
strictly
greater
than
3
.
1
Sho
w
that
:
6
×
2
p
−
2
≡
3
(
mo
d.
p
)
;
6
×
3
p
−
2
≡
2
(
mo
d.
p
)
2
Infer
that
:
6
·
u
p
−
2
≡
0
(
mo
d.
p
)
.
h
ttps:/
/c
hingmath.fr
sacados/4118
Extrait d'Amerique du Sud Novembre 2005
chapExoCorrec/3192
sacados/3192
chapExoCorrec/4275
sacados/4275
E.3252
1
Consider
the
equation
(
E
)
:
109
x
−
226
y
=
1
where
x
and
y
are
relativ
e
in
tegers.
a
Determine
the
pg
cd
of
109
and
226.
What
can
w
e
con-
clude
ab
out
the
equation
(
E
)
?
b
Sho
w
that
the
set
of
solutions
to
(
E
)
is
the
set
of
pairs
of
the
form
(
141+226
k
;
68+109
k
)
,
where
k
b
elongs
to
Z
.
Deduce
that
there
exists
a
unique
non-zero
natural
n
um
b
er
d
less
than
or
equal
to
226
and
a
unique
non-
zero
natural
n
um
b
er
e
suc
h
that
:
109
d
=
1+226
e
.
(The
values
of
the
inte
gers
d
and
e
wil
l
b
e
sp
e
cifie
d)
2
Demonstrate
that
227
is
a
prime
in
teger.
3
Note
A
the
set
of
227
natural
in
tegers
a
tels
that
:
a
226
.
Consider
the
t
w
o
functions
f
and
g
de
A
dans
A
définies
as
follo
ws
:
to
an
y
in
teger
of
A
,
f
asso
cie
the
remainder
of
the
Euclidean
division
of
a
109
par
227
;
to
an
y
in
teger
of
A
,
g
asso
ciates
the
remainder
of
the
Euclidean
division
of
a
141
par
227.
a
Chec
k
that
:
g
f
(0)
=
0
.
R
e
c
al
l
the
fol
lowing
r
esult
c
al
le
d
F
ermat’s
little
the
o-
r
em
:
Si
p
est
a
prime
in
teger
and
a
un
in
teger
not
divisible
b
y
p
alors
a
p
−
1
≡
1
(
mo
d.
p
)
b
Sho
w
that,
whatev
er
the
non-zero
in
teger
a
de
A
:
a
226
≡
1
(
mo
d.
227)
.
c
Using
1
b
,
deduce
that,
whatev
er
the
non-zero
in-
teger
a
of
A
:
g
f
(
a
)
=
a
.
What
can
w
e
sa
y
ab
out
:
f
g
(
a
)
=
a
?
E.3625
1
Consider
the
set
:
A
7
=
1
;
2
;
3
;
4
;
5
;
6
a
F
or
eac
h
elemen
t
of
A
7
write
in
the
table
in
the
ap-
p
endix
the
single
elemen
t
y
of
A
7
suc
h
that
:
a
·
y
≡
1
(
mo
d.
7)
.
b
F
or
x
relativ
e
in
tegers,
demonstrate
that
:
the
equation
3
x
≡
5
(
mo
d.
7)
is
equiv
alen
t
to
x
≡
4
(
mo
d.
7)
.
c
F
or
x
relativ
e
in
tegers,
sho
w
that
the
only
relativ
e
in-
tegers
x
solutions
to
the
equation
a
·
x
≡
0
(
mo
d.
7)
are
m
ultiples
of
7
.
2
Throughout
this
question,
p
is
a
prime
in
teger
greater
than
or
equal
to
3
.
W
e
consider
the
set
A
p
=
1
;
2
;
:::
;
p
−
1
of
non-zero
natural
in
tegers
strictly
less
than
p
.
Let
a
b
e
an
elemen
t
of
A
p
.
a
Chec
k
that
a
p
−
2
is
a
solution
to
the
equation
:
a
·
x
≡
1
(
mo
d.
p
)
.
b
W
e
note
r
the
remainder
in
the
Euclidean
division
of
a
p
−
2
b
y
p
.
Pro
v
e
that
r
is
the
unique
solution
x
in
A
p
,
of
the
equation
a
·
x
≡
1
(
mo
d.
p
)
.
c
Let
x
and
y
b
e
t
w
o
relativ
e
in
tegers.
Pro
v
e
that
x
·
y
≡
0
(
mo
d.
p
)
if,
and
only
if,
x
is
a
m
ultiple
of
p
where
y
is
a
m
ultiple
of
p
.
d
Application
:
p
=
31
.
Solv
e
the
equations
in
A
31
:
2
x
≡
1
(
mo
d.
31)
et
3
x
≡
1
(
mo
d.
31)
.
Using
the
previous
results,
solv
e
the
equation
:
Z
6
x
2
−
5
x
+
1
≡
0
(
mo
d.
31)
E.3867
Recall
the
prop
ert
y
,
kno
wn
as
F
er-
mat’s
little
theorem
:
ˇ
soit
p
a
prime
in
teger
and
a
a
prime
natural
n
um
b
er
with
p
;
then
a
p
−
1
−
1
est
divisible
b
y
p
ı.
1
So
p
un
o
dd
prime
in
teger.
a
Sho
w
that
there
exists
a
natural
n
um
b
er
k
,
non-zero,
suc
h
that
:
2
k
≡
1
(
mo
d.
p
)
.
b
So
k
is
a
non-zero
natural
n
um
b
er
suc
h
that
2
k
≡
1
(
mo
d.
p
)
et
is
n
un
a
natural
n
um
b
er.
Sho
w
that,
if
k
divides
n
,
then
:
2
n
≡
1
(
mo
d.
p
)
.
c
So
b
tel
that
2
b
≡
1
(
mo
d.
p
)
,
b
étan
t
the
smallest
non-
zero
in
teger
v
erifying
this
prop
ert
y
.
Sho
w,
using
Euclidean
division
of
n
b
y
b
,
that
:
si
2
n
≡
1
(
mo
d.
p
)
alors
b
divise
n
.
2
Let
q
b
e
an
o
dd
prime
in
teger
and
the
in
teger
A
=
2
q
−
1
.
Let
p
b
e
a
prime
factor
of
A
.
a
Pro
v
e
that
:
2
q
≡
1
(
mo
d.
p
)
b
Sho
w
that
p
is
o
dd.
c
Let
b
suc
h
that
2
b
≡
1
(
mo
d.
p
)
,
b
b
eing
the
smallest
non-zero
in
teger
satisfying
this
prop
ert
y
.
Sho
w,
using
1
,
that
b
divides
q
.
Deduce
that
b
=
q
.
d
Sho
w
that
q
divides
p
−
1
,
then
sho
w
that
p
≡
1
(
mo
d.
2
q
)
.
3
Let
A
1
=
2
17
−
1
.
Here
is
the
list
of
prime
n
um
b
ers
less
than
400
and
whic
h
are
of
the
form
34
m
+1
,
with
m
a
non-zero
in
teger
:
103,
137,
239,
307.
Deduce
that
A
1
is
prime.
h
ttps:/
/c
hingmath.fr
chapExoCorrec/3252
sacados/3252
Liban Juin 2005 5 points
sacados/3625
chapExoCorrec/3867
sacados/3867
E.3868
F
or
an
y
natural
n
um
b
er
n
sup
erior
or
equal
to
2
,
w
e
p
ose
:
A
(
n
)
=
n
4
+
1
The
ob
ject
of
the
exercise
is
to
study
the
prime
divisors
of
A
(
n
)
.
1
Some
results
:
a
Study
the
parit
y
of
the
in
teger
A
(11)
.
b
Sho
w
that,
whatev
er
the
in
teger
n
,
A
(
n
)
n
is
not
a
m
ultiple
of
3
.
c
Sho
w
that
an
y
in
teger
d
divisor
of
A
(
n
)
est
prime
with
n
.
d
Sho
w
that,
for
an
y
in
teger
d
divisor
of
A
(
n
)
:
n
8
≡
1
(
mo
d.
d
)
2
Criteria
searc
h
:
Let
d
b
e
a
divisor
of
A
(
n
)
.
W
e
denote
s
the
smallest
of
the
non-zero
natural
in
tegers
k
suc
h
as
:
n
k
≡
1
(
mo
d.
d
)
a
Let
k
b
e
suc
h
an
in
teger.
Using
the
Euclidean
division
of
k
b
y
s
,
sho
w
that
s
divides
k
.
b
Deduce
that
s
is
a
divisor
of
8
.
c
Sho
w
that
if,
in
addition,
d
is
prime,
then
s
is
a
divisor
of
d
−
1
.
F
ermat’s
little
theorem
can
b
e
used.
3
Searc
h
for
prime
divisors
of
A
(
n
)
in
the
case
where
n
is
an
ev
en
in
teger.
Let
p
b
e
a
prime
divisor
of
A
(
n
)
.
By
examining
the
cases
successiv
ely
:
s
=
1
;
s
=
2
;
s
=
4
conclude
that
p
is
congruen
t
to
1
mo
dulo
8.
4
In
this
question,
an
y
attempt
at
researc
h,
ev
en
if
incom-
plete,
will
b
e
tak
en
in
to
accoun
t
in
the
assessmen
t.
Apply
the
ab
o
v
e
to
find
the
prime
divisors
of
A
(12)
.
Note
:
the
list
of
prime
n
um
b
ers
congruen
t
to
1
mo
dulo
8
b
egins
with
17,
41,
73,
89,
97,
113,
137.
.
.
.
E.4327
W
e
recall
the
prop
ert
y
kno
wn
as
F
ermat’s
little
theorem
:
If
p
is
a
prime
in
teger
and
a
is
a
natural
in
teger
not
divisible
b
y
p
,
alors
a
p
−
1
≡
1
(
mo
d.
p
)
.
Consider
the
sequence
u
n
of
natural
in
tegers
defined
b
y
:
u
0
=
1
;
u
n
+1
=
10
·
u
n
+21
for
an
y
in
teger
n
∈
N
1
Calculate
u
1
,
u
2
et
u
3
.
2
a
Pro
v
e
b
y
recurrence
that,
for
an
y
natural
n
um
b
er
n
:
3
·
u
n
=
10
n
+1
−
7
b
Deduce,
for
an
y
natural
n
um
b
er
n
,
the
decimal
repre-
sen
tation
of
u
n
.
3
Sho
w
that
u
2
is
a
prime
in
teger.
W
e
no
w
prop
ose
to
study
the
divisibilit
y
of
the
terms
of
the
sequence
u
n
b
y
certain
prime
in
tegers.
4
Pro
v
e
that,
for
an
y
natural
n
um
b
er
n
,
u
n
is
not
divisible
b
y
2
,
3
,
or
5
.
5
a
Pro
v
e
that,
for
an
y
natural
n
um
b
er
n
:
3
·
u
n
≡
4
−
(
−
1)
n
(
mo
d.
11)
b
Deduce
that,
for
an
y
natural
n
um
b
er
n
,
u
n
is
not
di-
visible
b
y
11
.
6
a
Pro
v
e
the
equalit
y
:
10
16
≡
1
(
mo
d.
17)
.
b
Deduce
that,
for
an
y
natural
n
um
b
er
k
,
u
16
k
+8
is
di-
visible
b
y
17
.
E.8701
Determine
the
set
of
pairs
(
p
;
q
)
of
prime
in
tegers
v
erifying
suc
h
that
p
q
and
that
the
pro
duct
p
×
q
divides
the
sum
2
p
+2
q
7.
PPCM
E.3863
Throughout
the
exercise
x
and
y
denote
non-zero
natural
in
tegers
v
erifying
x
<
y
.
S
is
the
set
of
couples
(
x
;
y
)
suc
h
that
:
P
GC
D
(
x
;
y
)
=
y
−
x
1
a
Calculate
P
GC
D
(363
;
484)
.
b
Do
es
the
couple
(
363
;
484
)
b
elong
to
S
?
2
Let
n
b
e
a
non-zero
natural
n
um
b
er
;
do
es
the
pair
(
n
;
n
+1
)
b
elong
to
S
Justify
y
our
answ
er.
3
a
Sho
w
that
(
x
;
y
)
b
elongs
to
S
if,
and
only
if,
there
exists
a
non-zero
natural
n
um
b
er
k
suc
h
that
:
x
=
k
·
(
y
−
x
)
;
y
=
(
k
+
1)(
y
−
x
)
b
Deduce
that
for
an
y
pair
(
x
;
y
)
of
S
,
w
e
ha
v
e
:
P
P
C
M
(
x
;
y
)
=
k
·
(
k
+
1)
·
(
y
−
x
)
4
a
Determine
the
set
of
natural
n
um
b
ers
that
are
divi-
sors
of
228
.
b
Deduce
the
set
of
pairs
(
x
;
y
)
of
S
suc
h
that
:
P
P
C
M
(
x
;
y
)
=
228
E.4280
Consider
the
equation
(
F
)
:
x
2
−
52
·
x
+480
=
0
where
x
is
a
natural
n
um
b
er.
Sho
w
that
there
are
no
t
w
o
non-zero
natural
n
um
b
ers
whose
P
GC
D
and
P
P
C
M
are
solutions
of
the
equation
(
F
)
.
E.3864
1
Let
a
and
b
b
e
non-zero
natural
n
um
b
ers
suc
h
that
:
P
GC
D
(
a
+
b
;
a
·
b
)
=
p
where
p
is
a
prime
in
teger.
a
Demonstrate
that
p
divides
a
2
.
(Note
that
a
2
=
a
(
a
+
b
)
−
a
·
b
)
b
Deduce
that
p
divides
a
.
So,
similarly
,
w
e
see
that
p
divides
b
.
c
Demonstrate
that
P
GC
D
(
a
;
b
)
=
p
.
2
W
e
denote
b
y
a
and
b
natural
n
um
b
ers
suc
h
that
a
b
.
a
Solv
e
the
system
:
P
GC
D
(
a
;
b
)
=
5
P
P
C
M
(
a
;
b
)
=
170
b
Deduce
the
solutions
of
the
system
:
P
GC
D
(
a
+
b
;
a
·
b
)
=
5
P
P
C
M
(
a
;
b
)
=
170
h
ttps:/
/c
hingmath.fr
sacados/3868
chapExoCorrec/4327
sacados/4327
Polynesie Juin 2011 7 points A voir dans quelle categorie le mettre
chapExoCorrec/8701
sacados/8701
chapExoCorrec/3863
sacados/3863
chapExoCorrec/4280
sacados/4280
Extrait de Liban Juin 2010
sacados/3864
Antilles guyane Septembre 2001 5 points
ChingMath
by ChingLab
©
Middle School
Grade 6
Grade 7
Grade 8
Grade 9
High School
Grade 10
Grade 11
Grade 12
Grade 12 opt. Complémentaire
Grade 12 opt. Experte
Various
Contact me
F.A.Q
Other website
ChingWeb