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
Grade 12 - Exp.
/ Annals on PGCD
35 exercises (including 32 corrected)
a
PGCD, property and congruence
(5 exercices)
Bezout's theorem
(2 exercices)
Gauss's theorem
(2 exercices)
Diophantine equation
(7 exercices)
Coding problem
(2 exercices)
Arithmetic and geometry
(2 exercices)
Arithmetic and sequences
(3 exercices)
1.
PGCD,
pr
op
erty
and
c
ongruenc
e
E.5284
1
a
Sho
w
that
3
n
3
−
11
n
+48
is
divisible
b
y
n
+
3
for
an
y
natural
n
um
b
er
n
.
b
Sho
w
that
3
n
2
−
9
n
+16
is
a
non-zero
natural
n
um
b
er
for
an
y
natural
n
um
b
er
n
.
2
Sho
w
that,
for
all
non-zero
natural
n
um
b
ers
a
,
b
and
c
,
the
follo
wing
equalit
y
is
true
:
pgcd
(
a
;
b
)
=
pgcd
(
b
·
c
−
a
;
b
)
3
Sho
w
that,
for
an
y
natural
n
um
b
er
n
,
greater
than
or
equal
to
2
,
the
equalit
y
is
true
:
pgcd
(
3
n
3
−
11
n
;
n
+3
)
=
pgcd
(
48
;
n
+3
)
4
a
Determine
the
set
of
natural
in
teger
divisors
of
48
.
b
Deduce
the
set
of
natural
in
tegers
n
suc
h
that
3
n
3
−
11
n
n
+3
is
a
natural
in
teger.
E.5285
The
sequences
of
natural
n
um
b
ers
x
n
and
y
n
are
defined
b
y
:
x
0
=
3
;
x
n
+1
=
2
·
x
n
−
1
y
0
=
1
;
y
n
+1
=
2
·
y
n
+
3
1
Demonstrate
b
y
recurrence
that
for
an
y
in
teger
n
∈
N
:
x
n
=
2
n
+1
+
1
2
a
Calculate
the
P
GC
D
of
x
8
and
x
9
,
then
that
of
x
2002
and
x
2003
.
What
can
w
e
deduce
from
this
for
x
8
and
x
9
on
the
one
hand,
and
for
x
2002
and
x
2003
on
the
other?
are
b
x
n
and
x
n
+1
prime
to
eac
h
other
for
an
y
natural
n
um-
b
er
n
?
3
a
Sho
w
that
for
an
y
natural
n
um
b
er
n
:
2
·
x
n
−
y
n
=
5
b
Express
y
n
in
terms
of
n
.
c
Using
congruences
mo
dulo
5
,
study
according
to
the
v
alues
of
the
natural
n
um
b
er
p
the
remainder
of
the
Euclidean
division
of
2
p
b
y
5
.
d
Note
d
n
the
P
GC
D
of
x
n
and
y
n
for
an
y
natural
n
um-
b
er
n
.
Sho
w
that
w
e
ha
v
e
d
n
=
1
or
d
n
=
5
;
deduce
the
set
of
natural
n
um
b
ers
n
suc
h
that
x
n
and
y
n
are
prime
to
eac
h
other.
E.3320
Consider
the
sequence
u
n
of
natural
n
um
b
ers
defined
b
y
:
u
0
=
14
u
n
+1
=
5
u
n
−
6
for
an
y
natural
n
um
b
er
n
1
Calculate
u
1
,
u
2
,
u
3
and
u
4
.
What
conjecture
can
b
e
made
ab
out
the
last
t
w
o
digits
of
u
n
?
2
Sho
w
that,
for
an
y
natural
n
um
b
er
n
:
u
n
+2
≡
u
n
(
mo
d.
4)
.
Deduce
that
for
an
y
natural
n
um
b
er
k
:
u
2
k
≡
2
(
mo
d.
4)
et
u
2
k
+1
≡
0
(
mo
d.
4)
3
a
Sho
w
b
y
recurrence
that,
for
an
y
in
teger
n
∈
N
:
2
·
u
n
=
5
n
+2
+
3
.
b
Deduce
that,
for
an
y
natural
n
um
b
er
n
:
2
u
n
≡
28
(
mo
d.
100)
.
4
Determine
the
last
t
w
o
digits
of
the
decimal
writing
of
u
n
according
to
the
v
alues
of
n
.
5
Sho
w
that
the
P
GC
D
of
t
w
o
consecutiv
e
terms
of
the
sequence
u
n
is
constan
t.
Sp
ecify
its
v
alue.
E.3719
P
art
A
Let
1
999
b
e
a
prime
in
teger.
Determine
the
set
of
pairs
(
a
;
b
)
of
natural
in
tegers
admitting
for
sum
11
994
and
for
P
GC
D
1
999
.
P
art
B
Consider
the
equation
(
E
)
of
unkno
wn
n
b
elonging
to
N
:
(
E
)
:
n
2
−
S
·
n
+11
994
=
0
où
S
is
a
natural
n
um
b
er.
W
e
are
in
terested
in
v
alues
of
S
suc
h
that
(
E
)
admits
t
w
o
solutions
in
N
.
1
Can
w
e
determine
an
in
teger
S
suc
h
that
3
is
a
solution
of
(
E
)
?
If
so,
sp
ecify
the
second
solution.
2
Can
w
e
determine
an
in
teger
S
suc
h
that
5
is
a
solution
of
(
E
)
?
3
Sho
w
that
an
y
in
teger
n
solution
of
(
E
)
is
a
divisor
of
11
994
.
Deduce
all
p
ossible
v
alues
of
S
suc
h
that
(
E
)
admits
t
w
o
in
teger
solutions.
P
art
C
Ho
w
w
ould
one
sho
w
that
1
999
is
a
prime
in
teger?
Sp
ecify
the
reasoning
used?
The
list
of
all
prime
in
tegers
less
than
100
is
sp
ecified
b
elo
w
:
2
;
3
;
5
;
7
;
11
;
13
;
17
;
19
23
;
31
;
37
;
41
;
43
;
47
;
53
;
59
61
;
67
;
71
;
73
;
79
;
83
;
89
;
97
h
ttps:/
/c
hingmath.fr
chapExoCorrec/5284
sacados/5284
Asie Juin 2003 4 points
chapExoCorrec/5285
sacados/5285
Liban Mai 2003 5 points
chapExoCorrec/3320
sacados/3320
chapExoCorrec/3719
sacados/3719
E.3246
In
this
exercise,
w
e
can
use
the
follo
wing
prop
osition
:
Prop
osition
:
ˇ
Giv
en
t
w
o
natural
n
um
b
ers,
a
and
b
,
b
oth
non-zero,
if
pgcd
(
a
;
b
)
=
1
then
pgcd
(
a
2
;
b
2
)
=
1
ı
A
sequence
(
S
n
)
is
defined
for
n
>
0
b
y
:
S
n
=
n
p
=1
p
3
.
W
e
prop
ose
to
calculate,
for
an
y
non-zero
natural
n
um
b
er
n
,
the
greatest
common
divisor
of
S
n
and
S
n
+1
.
1
Demonstrate
that,
for
an
y
n
>
0
,
w
e
ha
v
e
:
S
n
=
n
(
n
+1)
2
2
.
2
Study
the
case
where
n
is
ev
en.
Let
k
b
e
the
non-zero
natural
n
um
b
er
suc
h
that
n
=
2
k
.
a
Pro
v
e
that
:
pgcd
(
S
2
k
;
S
2
k
+1
)
=
(2
k
+
1)
2
·
pgcd
(
k
2
;
(
k
+
1)
2
)
.
b
Calculate
:
pgcd
(
k
;
k
+
1
)
.
c
Calculate
:
pgcd
(
S
2
k
;
S
2
k
+1
)
.
3
Study
the
case
where
n
is
o
dd.
Let
k
b
e
the
non-zero
natural
n
um
b
er
suc
h
that
n
=
2
k
+1
.
a
Pro
v
e
that
the
in
tegers
2
k
+1
and
2
k
+3
are
coprime.
b
Calculate
:
pgcd
(
S
2
k
+1
;
S
2
k
+2
)
.
4
Deduce
from
the
previous
questions
that
there
is
a
unique
v
alue
of
n
,
whic
h
w
e
will
determine,
for
whic
h
S
n
and
S
n
+1
are
coprime.
2.
Bezout’s
the
or
em
E.3226
In
this
exercise,
a
and
b
denote
strictly
p
ositiv
e
in
tegers.
1
a
Sho
w
that
if
there
are
t
w
o
in
tegers
u
and
v
suc
h
that
a
·
u
+
b
·
v
=
1
then
the
in
tegers
a
and
b
are
prime
to
eac
h
other.
b
Deduce
that
if
(
a
2
+
a
·
b
−
b
2
)
2
=
1
,
then
a
and
b
are
prime
to
eac
h
other.
2
W
e
prop
ose
to
determine
the
pairs
of
strictly
p
ositiv
e
in-
tegers
(
a
;
b
)
suc
h
that
(
a
2
+
a
·
b
−
b
2
)
2
=
1
.
Suc
h
a
pair
will
b
e
called
a
solution.
a
Determine
a
when
:
a
=
b
.
b
V
erify
that
(
1
;
1
)
,
(
2
;
3
)
and
(
5
;
8
)
are
three
particular
solutions.
c
Sho
w
that
if
(
a
;
b
)
is
a
solution
and
if
a
<
b
,
then
:
a
2
−
b
2
<
0
.
3
a
Sho
w
that
if
(
x
;
y
)
is
a
differen
t
solution
from
(
1
;
1
)
then
(
y
−
x
;
x
)
and
(
y
;
y
+
x
)
are
also
solutions.
b
Deduce
from
2
b
three
new
solutions.
4
Consider
the
sequence
of
strictly
p
ositiv
e
in
tegers
a
n
n
defined
b
y
a
0
=
a
1
=
1
and
for
an
y
in
teger
n
,
n
0
:
a
n
+2
=
a
n
+1
+
a
n
.
Sho
w
that
for
an
y
in
teger
n
0
,
(
a
n
;
a
n
+1
)
is
solution.
Deduce
that
the
in
tegers
a
n
and
a
n
+1
are
prime
to
eac
h
other.
E.3741
1
Monstrate
that,
for
an
y
non-zero
natural
n
um
b
er
k
and
for
an
y
natural
n
um
b
er
x
:
(
x
−
1)
·
1
+
x
+
x
2
+
·
·
·
+
x
k
−
1
=
x
k
−
1
Throughout
the
rest
of
the
exercise,
consider
an
in
teger
a
sup
erior
or
equal
to
2
.
2
a
So
n
a
non-zero
natural
n
um
b
er
and
d
un
p
ositiv
e
divisor
of
n
:
n
=
d
·
k
Sho
w
that
a
d
−
1
est
a
divisor
of
a
n
−
1
.
b
Deduce
from
the
previous
question
that
2
2004
−
1
est
divisible
b
y
7
,
b
y
63
puis
b
y
9
.
3
Let
m
and
n
b
e
t
w
o
non-zero
natural
n
um
b
ers
and
d
their
pg
cd
.
a
W
e
define
m
and
n
b
y
m
=
d
·
m
and
n
=
d
·
n
.
Apply-
ing
Bézout’s
theorem
to
m
and
n
,
sho
w
that
there
exist
relativ
e
in
tegers
u
and
v
suc
h
that
:
m
·
u
−
n
·
v
=
d
.
b
W
e
assume
that
u
and
v
are
strictly
p
ositiv
e.
Sho
w
that
:
a
m
·
u
−
1
−
a
n
·
v
−
1
·
a
d
=
a
d
−
1
Then
sho
w
that
a
d
−
1
is
the
pg
cd
of
:
a
m
·
u
−
1
et
a
n
·
v
−
1
.
c
Using
the
previous
result,
calculate
the
GCD
of
:
2
63
−
1
and
2
60
−
1
3.
Gauss’s
the
or
em
E.3630
Let
(
E
)
b
e
the
set
of
natural
in-
tegers
written,
in
base
10,
in
the
form
abba
où
a
is
a
digit
greater
than
or
equal
to
2
and
b
is
an
y
digit.
Examples
of
(
E
)
elemen
ts
:
2002
;
3773
;
9119
.
Num
b
er
of
(
E
)
elemen
ts
ha
ving
11
as
smallest
factor
premier
1
a
Decomp
ose
1001
in
to
a
pro
duct
of
prime
factors.
b
Sho
w
that
an
y
elemen
t
of
(
E
)
is
divisible
b
y
11
.
2
a
What
is
the
n
um
b
er
of
elemen
ts
in
(
E
)
?
b
What
is
the
n
um
b
er
of
elemen
ts
of
(
E
)
that
are
neither
divisible
b
y
2
nor
b
y
5
?
3
either
n
an
elemen
t
of
(
E
)
written
in
the
form
abba
.
a
Sho
w
that
:
ˇ
n
is
divisible
b
y
3
is
equiv
alen
t
to
a
+
b
is
divisible
b
y
3
ı
b
Sho
w
that
:
h
ttps:/
/c
hingmath.fr
chapExoCorrec/3246
sacados/3246
chapExoCorrec/3226
sacados/3226
chapExoCorrec/3741
sacados/3741
France Juin 2004 5 points
chapExoCorrec/3630
sacados/3630
ˇ
n
is
divisible
b
y
7
is
equiv
alen
t
to
b
is
divisible
b
y
7
ı
4
Deduce
from
the
previous
questions
the
n
um
b
er
of
ele-
men
ts
of
(
E
)
that
admit
11
as
the
smallest
prime
factor.
E.3837
Let
A
b
e
the
set
of
natural
in
tegers
in
the
in
terv
al
1
;
46]
.
1
Consider
the
equation
:
(
E
)
:
23
·
x
+
47
·
y
=
1
où
x
and
y
are
relativ
e
in
tegers.
a
Giv
e
a
particular
solution
x
0
;
y
0
of
(
E
)
.
b
Determine
the
set
of
couples
(
x
;
y
)
solutions
of
(
E
)
.
c
Deduce
that
there
exists
a
single
in
teger
x
b
elonging
to
A
suc
h
that
:
23
·
x
≡
1
(
mo
d.
47)
2
Let
a
and
b
b
e
t
w
o
relativ
e
in
tegers.
a
Sho
w
that
if
a
·
b
≡
0
(
mo
d.
47)
then
:
a
≡
0
(
mo
d.
47)
or
b
≡
0
(
mo
d.
47)
b
Deduce
that
if
a
2
≡
1
(
mo
d.
47)
then
:
a
≡
1
(
mo
d.
47)
;
a
≡
−
1
(
mo
d.
47)
3
a
Sho
w
that
for
an
y
in
teger
p
of
A
,
there
exists
a
rel-
ativ
e
in
teger
q
suc
h
that
:
p
×
q
≡
1
(
mo
d.
47)
.
F
or
the
rest,
w
e
admit
that
for
an
y
in
teger
p
of
A
,
there
exists
a
unique
in
teger,
denoted
inv
(
p
)
,
b
elonging
to
A
suc
h
that
:
p
×
inv
(
p
)
≡
1
(
mo
d.
47)
F
or
example
:
inv
(1)
=
1
car
1
×
1
≡
1
(
mo
d.
47)
inv
(2)
=
24
car
2
×
24
≡
1
(
mo
d.
47)
inv
(3)
=
16
car
3
×
16
≡
1
(
mo
d.
47)
b
What
are
the
in
tegers
p
of
A
that
v
erify
:
p
=
inv
(
p
)
c
Sho
w
that
:
46!
≡
−
1
(
mo
d.
47)
4.
Diophantine
e
quation
E.3198
P
art
A
:
Course
question
1
State
Bézout’s
theorem
and
Gauss’s
theorem.
2
Demonstrate
Gauss’s
theorem
using
Bézout’s
theorem.
P
art
B
This
in
v
olv
es
solving
in
Z
the
system
:
(
S
)
n
≡
13
(
mo
d.
19)
n
≡
6
(
mo
d.
12)
1
Demonstrate
that
there
exists
a
pair
(
u
;
v
)
of
relativ
e
in-
tegers
suc
h
that
:
19
u
+
12
v
=
1
(This
question
do
es
not
ask
for
an
example
of
such
a
c
ou-
ple)
V
erify
that
the
n
um
b
er
N
=
13
×
12
v
+6
×
19
u
is
a
solution
of
(
S
)
for
suc
h
a
couple.
2
a
Let
n
0
b
e
a
solution
of
(
S
)
,
c
hec
k
that
the
system
(
S
)
is
equiv
alen
t
to
:
n
≡
n
0
(
mo
d.
19)
n
≡
n
0
(
mo
d.
12)
b
Demonstrate
that
the
system
n
≡
n
0
(
mo
d.
19)
n
≡
n
0
(
mo
d.
12)
equals
:
n
≡
n
0
(
mo
d.
12
×
19)
.
3
a
Find
a
couple
(
u
;
v
)
solution
of
the
equation
19
u
+12
v
=
1
and
calculate
the
corresp
onding
N
v
alue.
b
Determine
the
set
of
solutions
of
(
S
)
(you
may
use
question
2
b
)
.
4
A
natural
n
um
b
er
n
is
suc
h
that
when
divided
b
y
12
the
remainder
is
6
and
when
divided
b
y
19
the
remainder
is
13
.
W
e
divide
n
b
y
228
=
12
×
19
.
What
is
the
remainder
r
of
this
division?
E.3258
Recall
that
2
003
is
a
prime
in
te-
ger.
1
a
Determine
t
w
o
relativ
e
in
tegers
u
and
v
suc
h
that
:
123
u
+
2003
v
=
1
b
Deduce
a
relativ
e
in
teger
k
0
suc
h
that
:
123
k
0
≡
1
(
mo
d.
2003)
c
Sho
w
that,
for
an
y
relativ
e
in
teger
x
,
123
x
≡
456
(
mo
d.
2003)
if,
and
only
if,
x
≡
456
k
0
(
mo
d.
2003)
d
Sho
w
that
there
exists
a
unique
in
teger
n
suc
h
that
:
1
n
2002
et
123
n
≡
456
(
mo
d.
2003)
2
Let
a
b
e
an
in
teger
suc
h
that
:
1
a
2002
a
Determine
:
pgcd
(
a
;
2003
)
Deduce
that
there
exists
an
in
teger
m
suc
h
that
:
a
·
m
≡
1
(
mo
d.
2003)
b
Sho
w
that,
for
an
y
in
teger
b
,
there
exists
a
single
in
te-
ger
x
suc
h
that
:
0
x
2
002
;
a
·
x
≡
b
(
mo
d.
2003)
h
ttps:/
/c
hingmath.fr
chapExoCorrec/3837
sacados/3837
chapExoCorrec/3198
sacados/3198
chapExoCorrec/3258
sacados/3258
France Septembre 2003 5 points
E.3256
Let
b
e
the
equation
(1)
of
rational
unkno
wn
x
:
78
x
3
+
u
·
x
2
+
v
·
x
−
14
=
0
où
u
and
v
are
relativ
e
in
tegers.
1
It
is
assumed
in
this
question
that
14
39
is
a
solution
to
the
equation
(1)
.
a
Pro
v
e
that
the
in
tegers
u
and
v
are
related
b
y
the
re-
lation
:
14
u
+
39
v
=
1129
b
Use
Euclid’s
algorithm,
detailing
the
v
arious
steps
in
the
calculation,
to
find
a
pair
(
x
;
y
)
of
relativ
e
in
tegers
v
erifying
the
equation
:
14
x
+
39
y
=
1
V
erify
that
the
couple
(
−
25
;
9
)
is
a
solution
to
this
equation.
c
Deduce
a
couple
(
u
0
;
v
0
)
particular
solution
of
the
equation
:
14
u
+
39
v
=
1129
Giv
e
the
general
solution
of
this
equation,
i.e.
the
set
of
pairs
(
u
;
v
)
of
relativ
e
in
tegers
that
v
erify
it.
d
Determine,
among
the
preceding
couples
(
u
;
v
)
,
the
one
for
whic
h
the
in
teger
u
is
the
smallest
p
ossible
natural
n
um
b
er.
2
a
Decomp
ose
78
and
14
in
to
prime
factors.
Deduce,
in
N
,
the
set
of
divisors
of
78
and
the
set
of
divisors
of
14.
b
Let
P
Q
b
e
a
rational
solution
of
the
equation
(1)
of
unkno
wn
x
:
78
x
3
+
ux
2
+
v
x
−
14
=
0
où
u
and
v
are
relativ
e
in
tegers.
Sho
w
that
if
P
and
Q
are
relativ
e
in
tegers
prime
to
eac
h
other,
then
P
divides
14
and
Q
divides
78.
c
Deduce
the
n
um
b
er
of
rationals,
not
in
tegers,
that
can
b
e
solutions
of
the
equation
(1)
and
write,
among
these
rationals,
the
set
of
those
that
are
p
ositiv
e.
E.3477
The
parts
A
and
B
are
indep
en-
den
t.
P
art
A
Consider
the
equation
(
E
)
:
7
x
−
6
y
=
1
où
x
and
y
are
natural
n
um
b
ers.
1
Giv
e
a
particular
solution
of
the
equation
(
E
)
.
2
Determine
the
set
of
pairs
of
natural
n
um
b
ers
that
are
solutions
of
the
equation
(
E
)
.
P
art
B
In
this
part,
w
e
prop
ose
to
determine
the
couples
(
n
;
m
)
of
non-zero
natural
n
um
b
ers
v
erifying
the
relation
:
7
n
−
3
×
2
m
=
1
(
F
)
1
W
e
assume
m
4
.
Sho
w
that
there
are
exactly
t
w
o
solution
pairs.
2
It
is
no
w
assumed
that
m
5
.
a
Sho
w
that
if
the
couple
(
n
;
m
)
v
erifies
the
relation
(
F
)
then
:
7
n
≡
1
(
mo
d.
32)
b
By
studying
the
remainders
of
the
division
b
y
32
of
the
p
o
w
ers
of
7
,
sho
w
that
if
the
pair
(
n
;
m
)
v
erifies
the
relation
(
F
)
then
n
is
divisible
b
y
4.
c
Deduce
that
if
the
couple
(
n
;
m
)
v
erifies
the
relation
(
F
)
then
:
7
n
≡
1
(
mo
d.
5)
.
d
F
or
m
5
,
are
there
pairs
(
n
;
m
)
of
natural
n
um
b
ers
v
erifying
the
relation
(
F
)
?
3
Conclude,
i.e.
determine
the
set
of
pairs
of
non-zero
nat-
ural
in
tegers
v
erifying
the
relation
(
F
)
.
E.3905
Questions
1
and
2
are
inde-
p
enden
t.
Let
n
b
e
a
non-zero
natural
n
um
b
er.
1
Consider
the
equation
noted
(
E
)
:
3
x
+
7
y
=
10
2
n
où
x
and
y
are
relativ
e
in
tegers.
a
Determine
a
pair
(
u
;
v
)
of
relativ
e
in
tegers
suc
h
that
:
3
·
u
+
7
·
v
=
1
Deduce
a
particular
solution
(
x
0
;
y
0
)
of
the
equation
(
E
)
.
b
Determine
the
set
of
pairs
of
relativ
e
in
tegers
(
x
;
y
)
solutions
of
(
E
)
.
2
Consider
the
equation
noted
(
G
)
:
3
x
2
+
7
y
2
=
10
2
n
où
x
and
y
are
relativ
e
in
tegers.
a
Sho
w
that
:
100
≡
2
(
mo
d.
7)
.
Sho
w
that
if
(
x
;
y
)
is
a
solution
of
(
G
)
then
:
3
x
2
≡
2
n
(
mo
d.
7)
.
b
Repro
duce
and
complete
the
follo
wing
table
:
Reste
of
the
division
euclidean
of
x
b
y
7
0
1
2
3
4
5
6
Reste
of
the
division
euclidienne
of
3
x
2
b
y
7
c
Sho
w
that
2
n
is
congruen
t
to
1
,
2
or
4
mo
dulo
7
.
Deduce
that
the
equation
(
G
)
admits
no
solution.
h
ttps:/
/c
hingmath.fr
chapExoCorrec/3256
sacados/3256
Antilles-Guyane Septembre 2003 4 points
chapExoCorrec/3477
sacados/3477
chapExoCorrec/3905
sacados/3905
E.5432
P
art
A
-
Organized
restitu-
tion
of
kno
wledge
Prerequisites
:
Bézout’s
theorem
and
Gauss’s
theorem
are
recalled
b
elo
w.
Bézout’s
theorem
:
T
w
o
relativ
e
in
tegers
a
and
b
are
prime
to
eac
h
other
if,
and
only
if,
there
exists
a
pair
(
u
;
v
)
of
relativ
e
in
tegers
satisfying
a
·
u
+
b
·
v
=
1
.
Gauss’s
theorem
:
Let
a
,
b
,
and
c
b
e
relativ
e
in
tegers.
If
a
divides
the
pro
duct
b
·
c
and
if
a
and
b
are
relativ
ely
prime,
then
a
divides
c
1
Using
Bézout’s
theorem,
pro
v
e
Gauss’s
theorem.
2
Let
p
and
q
b
e
t
w
o
natural
in
tegers
suc
h
that
p
and
q
are
relativ
ely
prime.
Deduce
from
Gauss’s
theorem
that
if
a
is
a
relativ
e
in-
teger
suc
h
that
a
≡
0
(
mo
d.
p
)
and
a
≡
0
(
mo
d.
q
)
,
then
a
≡
0
(
mo
d.
pq
)
P
art
B
W
e
prop
ose
to
determine
the
set
S
of
relativ
e
in
tegers
n
sat-
isfying
the
system
:
n
≡
9
(
mo
d.
17)
n
≡
3
(
mo
d.
5)
1
Searc
h
for
an
elemen
t
of
S
.
W
e
denote
b
y
(
u
;
v
)
a
pair
of
relativ
e
in
tegers
suc
h
that
:
17
·
u
+5
·
v
=
1
a
Justify
the
existence
of
suc
h
a
pair
(
u
;
v
)
.
b
W
e
set
:
n
0
=
3
×
17
u
+9
×
5
v
Pro
v
e
that
n
0
b
elongs
to
S
.
c
Giv
e
an
example
of
an
in
teger
n
0
b
elonging
to
S
.
2
Characterization
of
the
elemen
ts
of
S
.
a
Let
n
b
e
a
relativ
e
in
teger
b
elonging
to
S
.
Pro
v
e
that
:
n
−
n
0
≡
0
(
mo
d.
85)
.
b
Deduce
that
a
relativ
e
in
teger
n
b
elongs
to
S
if,
and
only
if,
it
can
b
e
written
in
the
form
n
=43+85
k
where
k
is
a
relativ
e
in
teger.
3
Application.
Zo
e
kno
ws
she
has
b
et
w
een
300
and
400
tok
ens.
If
she
mak
es
piles
of
17
tok
ens,
she
has
9
left.
If
she
mak
es
piles
of
5
tok
ens,
she
has
3
left.
Ho
w
man
y
tok
ens
do
es
she
ha
v
e?
E.3322
1
a
What
is
the
remainder
of
the
Euclidean
division
of
6
10
b
y
11
?
Justify
.
b
What
is
the
remainder
of
the
Euclidean
division
of
6
4
b
y
5?
Justify
.
c
Deduce
the
t
w
o
congruences
:
6
40
≡
1
(
mo
d.
11)
;
6
40
≡
1
(
mo
d.
5)
.
d
Sho
w
that
6
40
−
1
is
divisible
b
y
55
.
2
In
this
question
x
and
y
denote
relativ
e
in
tegers.
a
Sho
w
that
the
equation
:
(
E
)
:
65
·
x
−
40
·
y
=
1
has
no
solution.
b
Sho
w
that
the
equation
:
(
E
)
:
17
·
x
−
40
·
y
=
1
admits
at
least
one
solution.
c
Using
Euclid’s
algorithm,
determine
a
pair
of
relativ
e
in
tegers
that
are
solutions
of
the
equation
(
E
)
.
d
Solv
e
the
equation
(
E
)
.
Deduce
that
there
exists
a
unique
natural
x
0
less
than
40
suc
h
that
:
17
x
0
≡
1
(
mo
d.
40)
3
F
or
an
y
natural
n
um
b
er
a
,
sho
w
that
:
Si
a
17
≡
b
(
mo
d.
55)
a
40
≡
1
(
mo
d.
55)
then
b
33
≡
a
(
mo
d.
55)
5.
Co
ding
pr
oblem
E.5456
P
art
A
:
Organized
kno
wledge
transfer
Let
a
,
b
,
c
,
d
b
e
relativ
e
in
tegers
and
n
a
non-zero
natural
n
um
b
er.
Sho
w
that
if
a
≡
b
(
mo
d.
n
)
and
if
c
≡
d
(
mo
d.
n
)
then
ac
≡
bd
(
mo
d.
n
)
.
P
art
B
:
In
v
erse
of
23
mo
dulo
26
Consider
the
equation
:
(
E
)
:
23
x
−
26
y
=
1
où
x
and
y
denote
t
w
o
relativ
e
in
tegers.
1
V
erify
that
the
pair
(
−
9
;
−
8
)
is
a
solution
of
equation
(
E
)
.
2
Then
solv
e
the
equation
(
E
)
.
3
Deduce
an
in
teger
a
suc
h
that
:
0
a
25
;
23
a
≡
1
(
mo
d.
26)
P
art
C
:
Hill
encryption
W
e
w
an
t
to
enco
de
a
t
w
o-letter
w
ord
according
to
the
follo
w-
ing
pro
cedure
:
Step
1
Eac
h
letter
of
the
w
ord
is
replaced
b
y
an
in
teger
using
the
table
b
elo
w
:
A
B
C
D
E
F
G
H
I
J
K
L
M
0
1
2
3
4
5
6
7
8
9
10
11
12
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
13
14
15
16
17
18
19
20
21
22
23
24
25
W
e
obtain
a
pair
of
in
tegers
(
x
1
;
x
2
)
où
x
1
corresp
onds
to
the
first
letter
of
the
w
ord
and
x
2
corresp
onds
to
the
second
letter
of
the
w
ord.
Step
2
(
x
1
;
x
2
)
is
transformed
in
to
(
y
1
;
y
2
)
suc
h
that
:
(
S
1
)
:
y
1
≡
11
x
1
+
3
x
2
(
mo
d.
26)
y
2
≡
7
x
1
+
4
x
2
(
mo
d.
26)
with
0
y
1
25
and
0
y
2
25
Step
3
(
y
1
;
y
2
)
is
transformed
in
to
a
t
w
o-letter
w
ord
us-
ing
the
mapping
table
giv
en
in
step
1
.
Example
:
h
ttps:/
/c
hingmath.fr
chapExoCorrec/5432
sacados/5432
chapExoCorrec/3322
sacados/3322
chapExoCorrec/5456
sacados/5456
TE
mot
en
clair
étap
e
1
=
⇒
(
19
;
4
)
étap
e
2
=
⇒
(
13
;
19
)
étap
e
3
=
⇒
NT
mot
co
dé
1
Co
de
the
w
ord
S
T
.
2
No
w
w
e
w
an
t
to
determine
the
deco
ding
pro
cedure
:
a
Sho
w
that
an
y
pair
(
x
1
;
x
2
)
v
erifying
the
equations
of
the
system
(
S
1
)
,
v
erifies
the
equations
of
the
system
:
(
S
2
)
:
23
x
1
≡
4
y
1
+
23
y
2
(
mo
d.
26)
23
x
2
≡
19
y
1
+
11
y
2
(
mo
d.
26)
b
Using
part
B
,
sho
w
that
an
y
pair
(
x
1
;
x
2
)
v
erifying
the
equations
of
the
system
(
S
2
)
,
v
erifies
the
equations
of
the
system
:
(
S
3
)
:
x
1
≡
16
y
1
+
y
2
(
mo
d.
26)
x
2
≡
11
y
1
+
5
y
2
(
mo
d.
26)
c
Sho
w
that
an
y
pair
(
x
1
;
x
2
)
v
erifying
the
equations
of
the
system
(
S
3
)
,
v
erifies
the
equations
of
the
system
(
S
1
)
.
d
Deco
de
w
ord
Y
J
E.3324
P
art
A
Consider
the
equation
(
E
)
:
11
x
−
26
y
=
1
,
où
x
and
y
denote
t
w
o
relativ
e
in
tegers.
1
Chec
k
that
the
torque
(
−
7
;
−
3
)
is
solution
of
(
E
)
.
2
Then
solv
e
equation
(
E
)
.
3
Deduce
the
pair
of
relativ
e
in
tegers
(
u
;
v
)
solution
of
(
E
)
suc
h
that
:
0
u
25
.
P
art
B
Eac
h
letter
of
the
alphab
et
is
treated
as
an
in
teger,
as
sho
wn
in
the
table
b
elo
w
:
A
B
C
D
E
F
G
H
I
J
K
L
M
0
1
2
3
4
5
6
7
8
9
10
11
12
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
13
14
15
16
17
18
19
20
21
22
23
24
25
W
e
ˇ
co
de
ı
an
y
in
teger
x
b
et
w
een
0
and
25
as
follo
ws
:
W
e
calculate
11
x
+8
.
W
e
calculate
the
remainder
of
the
Euclidean
division
of
11
x
+8
b
y
26,
whic
h
w
e
call
y
.
x
is
then
ˇ
co
dé
ı
b
y
y
.
So,
for
example,
the
letter
L
is
equated
with
the
in
teger
11
;
11
×
11+8
=
129
or
129
≡
25
(
mo
d.
26)
;
25
is
the
remainder
of
the
Euclidean
division
of
129
b
y
26.
The
in
teger
25
corre-
sp
onds
to
the
letter
Z
.
The
letter
L
is
therefore
enco
ded
b
y
the
letter
Z
.
1
Co
de
letter
W
.
2
The
aim
of
this
question
is
to
determine
the
deco
ding
function.
a
Sho
w
that
for
all
relativ
e
in
tegers
x
and
j
,
w
e
ha
v
e
:
11
·
x
≡
j
(
mo
d.
26)
is
equiv
alen
t
to
x
≡
19
·
j
(
mo
d.
26)
.
b
Deduce
a
deco
ding
pro
cedure.
c
Deco
de
the
letter
W
.
6.
A
rithmetic
and
ge
ometry
E.3264
1
a
Let
p
b
e
a
natural
n
um
b
er.
Sho
w
that
one
of
the
three
in
tegers
p
,
p
+10
and
p
+20
,
and
only
one
is
di-
visible
b
y
3.
b
The
natural
in
tegers
a
,
b
and
c
are,
in
this
order,
the
first
three
terms
of
an
arithmetic
sequence
of
reason
10.
Determine
these
three
in
tegers
kno
wing
that
they
are
prime.
2
Let
E
b
e
the
set
of
triplets
of
relativ
e
in
tegers
(
u
;
v
;
w
)
suc
h
that
:
3
·
u
+
13
·
v
+
23
·
w
=
0
a
Sho
w
that
for
suc
h
a
triplet
:
v
≡
w
(
mo
d.
3)
b
W
e
p
ose
v
=
3
k
+
r
and
w
=
3
k
+
r
où
k
,
k
and
r
are
relativ
e
in
tegers
and
0
r
2
.
Sho
w
that
the
elemen
ts
of
E
are
of
the
form
:
−
13
k
−
23
k
−
12
r
;
3
k
+
r
;
3
k
+
r
c
Space
is
referred
to
an
orthonormal
frame
of
refer-
ence
of
origin
O
and
let
P
b
e
the
plane
of
equation
3
x
+13
y
+23
z
=
0
.
Determine
the
set
of
p
oin
ts
M
with
co
ordinates
(
x
;
y
;
z
)
relativ
e
in
tegers
b
elonging
to
the
plane
P
and
lo
cated
inside
the
cub
e
of
cen
ter
O
,
of
side
5
and
whose
edges
are
parallel
to
the
axes.
h
ttps:/
/c
hingmath.fr
chapExoCorrec/3324
sacados/3324
Antilles-Guyane Juin 2008 5 points
chapExoCorrec/3264
sacados/3264
-1
2
3
4
5
6
7
8
9
I
-1
2
3
4
5
6
7
8
9
J
O
E.3325
Let
a
and
b
b
e
t
w
o
non-zero
nat-
ural
n
um
b
ers
;
the
set
of
p
oin
ts
in
the
plane
is
called
ˇ
réseau
ı
asso
ciated
with
the
in
tegers
a
and
b
,
pro
vided
with
an
or-
thonormal
reference
frame,
whose
co
ordinates
(
x
;
y
)
are
in
te-
gers
satisfying
the
conditions
:
0
x
a
;
0
y
b
W
e
note
R
a,b
this
net
w
ork.
The
aim
of
the
exercise
is
to
relate
certain
arithmetic
prop-
erties
of
the
in
tegers
x
and
y
to
geometric
prop
erties
of
the
corresp
onding
p
oin
ts
on
the
net
w
ork.
A
-
Graphical
represen
tation
of
some
sets
In
this
question,
answ
ers
are
exp
ected
without
explanation,
in
the
form
of
a
graph
to
b
e
duly
completed
on
the
attac
hed
sheet
to
b
e
returned
with
the
cop
y
.
Graphically
represen
t
the
p
oin
ts
M
(
x
;
y
)
of
the
net
w
ork
R
8.8
v
erifying
:
1
x
≡
2
(
mo
d.
3)
and
y
≡
1
(
mo
d.
3)
,
on
graph
1
of
the
app
endix
sheet.
2
x
+
y
≡
1
(
mo
d.
3)
,
on
graph
2
of
the
app
endix
sheet.
3
x
≡
y
(
mo
d.
3)
,
on
graph
3
of
the
app
endix
sheet.
B
-
Solving
an
equation
Consider
the
equation
(
E
)
:
7
x
−
4
y
=
1
,
où
where
the
un-
kno
wns
x
and
y
are
relativ
e
in
tegers.
1
Determine
a
pair
of
relativ
e
in
tegers
(
x
0
;
y
0
)
solution
of
the
equation
(
E
)
.
2
Determine
the
set
of
pairs
of
relativ
e
in
tegers
solutions
of
the
equation
(
E
)
.
3
Sho
w
that
the
equation
(
E
)
admits
a
unique
solution
(
x
;
y
)
for
whic
h
the
corresp
onding
p
oin
t
M
(
x
;
y
)
b
elongs
to
the
lattice
R
4.7
.
C
-
A
prop
ert
y
of
p
oin
ts
lo
cated
on
the
diagonal
of
the
net
w
ork.
If
a
and
b
are
t
w
o
non-zero
natural
n
um
b
ers,
consider
the
diagonal
[
O
A
]
of
the
R
anetw
or
k
,b
with
O
(
0
;
0
)
and
A
(
a
;
b
)
.
1
Sho
w
that
the
p
oin
ts
of
the
segmen
t
[
O
A
]
are
c
haracter-
ized
b
y
the
conditions
:
0
x
a
;
0
y
b
;
a
·
y
=
b
·
x
2
Sho
w
that
if
a
and
b
are
prime
to
eac
h
other,
then
the
p
oin
ts
O
and
A
are
the
only
p
oin
ts
on
the
segmen
t
[
O
A
]
b
elonging
to
the
net
w
ork
R
a,b
.
3
Sho
w
that
if
a
and
b
are
not
prime
to
eac
h
other,
then
the
segmen
t
[
O
A
]
con
tains
at
least
one
other
net
w
ork
p
oin
t.
(Consider
the
gc
d
d
of
the
inte
gers
a
and
b
and
set
a
=
d
·
a
and
b
=
d
·
b
)
Graphique
1
Graphique
2
Graphique
3
h
ttps:/
/c
hingmath.fr
chapExoCorrec/3325
sacados/3325
Asie Juin 2008 5 points
-1
2
3
4
5
6
7
8
9
I
-1
2
3
4
5
6
7
8
9
J
O
-1
2
3
4
5
6
7
8
9
I
-1
2
3
4
5
6
7
8
9
J
O
-1
2
3
4
5
6
7
8
9
I
-1
2
3
4
5
6
7
8
9
J
O
7.
A
rithmetic
and
se
quenc
es
E.3254
Consider
the
sequence
u
n
of
natural
n
um
b
ers
defined
b
y
:
u
0
=
14
u
n
+1
=
5
u
n
−
6
for
an
y
natural
n
um
b
er
n
1
Calculate
u
1
,
u
2
,
u
3
and
u
4
.
What
conjecture
can
b
e
made
ab
out
the
last
t
w
o
digits
of
u
n
?
2
Sho
w
that,
for
an
y
natural
n
um
b
er
n
:
u
n
+2
≡
u
n
(
mo
d.
4)
.
Deduce
that
for
an
y
natural
n
um
b
er
k
:
u
2
k
≡
2
(
mo
d.
4)
et
u
2
k
+1
≡
0
(
mo
d.
4)
.
3
a
Sho
w
b
y
recurrence
that,
for
an
y
n
∈
N
:
2
u
n
=
5
n
+2
+
3
.
b
Deduce
that,
for
an
y
natural
n
um
b
er
n
:
2
u
n
≡
28
(
mo
d.
100)
.
4
Determine
the
last
t
w
o
digits
of
the
decimal
writing
of
u
n
according
to
the
v
alues
of
n
.
5
Sho
w
that
the
P
GC
D
of
t
w
o
consecutiv
e
terms
of
the
sequence
(
u
n
)
is
constan
t.
Sp
ecify
its
v
alue.
E.3574
1
Calculate
the
P
GC
D
of
4
5
−
1
and
4
6
−
1
.
Let
u
b
e
the
n
umerical
sequence
defined
b
y
:
u
0
=
0
u
1
=
1
u
n
+2
=
5
·
u
n
+1
−
4
·
u
n
for
an
y
natural
n
um
b
er
n
2
Calculate
the
terms
u
2
,
u
3
and
u
4
of
the
sequence
u
.
3
a
Sho
w
that
the
sequence
u
v
erifies,
for
an
y
natural
n
um
b
er
n
:
u
n
+1
=
4
·
u
n
+
1
b
Sho
w
that,
for
an
y
natural
n
um
b
er
n
,
u
n
is
a
natural
n
um
b
er.
c
Deduce,
for
an
y
natural
n
um
b
er
n
,
the
P
GC
D
of
u
n
and
u
n
+1
.
4
Let
v
b
e
the
sequence
defined
for
an
y
an
turel
in
teger
n
b
y
:
v
n
=
u
n
+
1
3
a
Sho
w
that
v
is
a
geometric
sequence
whose
reason
and
first
term
v
0
will
b
e
determined.
b
Express
v
n
then
u
n
as
a
function
of
n
.
c
Determine,
for
an
y
natural
n
um
b
er
n
,
the
P
GC
D
of
4
n
+1
−
1
and
of
4
n
−
1
.
E.6252
Consider
the
function
f
of
an
algorithm
taking
as
argumen
t
t
w
o
natural
in
tegers
A
and
B
v
erifying
A
<
B
:
Function
f(A,B)
D
←
B
−
A
As
long
as
D
>
0
B
←
of
A
A
←
from
D
If
B
>
A
Then
D
←
from
B
−
A
Otherwise
D
←
from
A
−
B
End
If
End
As
long
as
Return
A
1
W
e
call
the
function
f
with
argumen
t
v
alues
:
A
=
12
and
B
=
14
.
W
e
will
complete
the
table
b
elo
w
b
y
indicating
the
suc-
cessiv
e
v
alues
tak
en
b
y
the
v
ariables
A
,
B
and
D
during
the
call
to
this
function.
A
B
D
12
14
2
Calling
the
function
f
calculates
the
P
GC
D
v
alue
of
the
n
um
b
ers
A
and
B
.
By
en
tering
A
=
221
and
B
=
331
,
the
call
to
the
f
function
returns
the
v
alue
1
.
a
justify
that
there
exist
couples
(
x
;
y
)
of
relativ
e
in
te-
gers
solutions
of
the
equation
:
(
E
)
:
221
·
x
−
331
·
y
=
1
b
V
erify
that
the
couple
(
3
;
2
)
is
a
solution
of
the
equa-
tion
(
E
)
.
Deduce
the
set
of
couples
(
x
;
y
)
of
relativ
e
in
tegers
so-
lutions
of
the
equation
(
E
)
.
3
Consider
the
sequences
of
natural
n
um
b
ers
u
n
and
v
n
defined
for
an
y
natural
n
um
b
er
n
b
y
:
u
n
=
2
+
221
·
n
;
v
0
=
3
v
n
+1
=
v
n
+
331
a
Express
v
n
as
a
function
of
the
natural
n
um
b
er
n
.
b
Determine
all
pairs
of
natural
n
um
b
ers
(
p
;
q
)
suc
h
that
:
u
p
=
v
q
;
0
p
500
;
0
q
500
8.
Unclassifie
d
financial
ye
ars
h
ttps:/
/c
hingmath.fr
chapExoCorrec/3254
sacados/3254
chapExoCorrec/3574
sacados/3574
chapExoCorrec/6252
sacados/6252
A
B
C
D
E
F
G
H
E.1604
F
or
eac
h
of
the
follo
wing
fiv
e
prop
ositions,
indicate
whether
it
is
true
or
false
and
giv
e
a
demonstration
of
the
c
hosen
answ
er.
An
unpro
v
en
answ
er
scores
no
p
oin
ts,
Prop
osition
1
:
P
our
an
y
natural
n
um
b
er
n
,
3
divides
the
natural
n
um
b
er
2
2
n
−
1
Prop
osition
2
:
Si
a
relativ
e
in
teger
x
is
solution
of
equation
x
2
+
x
≡
0
(
mo
d.
6)
then
x
≡
0
(
mo
d.
3)
Prop
osition
3
:
L
the
set
of
pairs
of
relativ
e
in
tegers
(
x
;
y
)
solutions
of
the
equation
12
·
x
−
5
·
y
=
3
is
the
set
of
cou-
ples
(
4+10
·
k
;
9+24
·
k
)
where
k
∈
Z
Prop
osition
4
:
Il
exists
a
single
pair
(
a
;
b
)
of
natural
n
um-
b
ers,
suc
h
that
:
a
<
b
and
P
P
C
M
(
a
;
b
)
−
P
GC
D
(
a
;
b
)
=
1
T
w
o
natural
n
um
b
ers
M
and
N
are
suc
h
that
M
is
written
abc
in
base
ten
and
N
is
written
bca
in
base
ten.
Prop
osition
5
:
Si
the
in
teger
M
is
divisible
b
y
27
then
the
in
teger
M
−
N
is
also
divisible
b
y
27
.
E.3133
1
Consider
the
equation
:
(
E
)
:
17
x
−
24
y
=
9
where
(
x
;
y
)
is
a
pair
of
relativ
e
in
tegers.
a
V
erify
that
the
couple
(
9
;
6
)
is
solution
of
the
equation
(
E
)
.
b
Solv
e
equation
(
E
)
.
2
A
t
a
funfair,
John
sits
on
a
circular
merry-go-round
rep-
resen
ted
b
y
the
diagram
in
App
endix
2.
He
can
sit
on
an
y
of
the
eigh
t
p
oin
ts
indicated
on
the
circle.
The
merry-go-round
features
a
game
that
consists
in
catc
hing
a
p
om-p
om
whic
h,
mo
v
es
on
a
cable
forming
a
square
in
whic
h
the
circle
is
inscrib
ed.
The
merry-go-
round
turns
clo
c
kwise
at
constan
t
sp
eed.
It
mak
es
one
rev
olution
at
constan
t
sp
eed.
It
mak
es
one
rev
olution
in
24
seconds.
The
p
om-p
om
mo
v
es
in
the
same
direction
at
constan
t
sp
eed.
It
mak
es
one
turn
in
17
seconds.
T
o
win,
John
m
ust
catc
h
the
p
om-p
om,
and
he
can
only
do
so
at
the
con
tact
p
oin
ts
whic
h
are
noted
A
,
B
,
C
and
D
on
the
dra
wing.
A
t
time
t
=
0
,
John
starts
from
p
oin
t
H
at
the
same
time
as
the
p
om-p
om
starts
from
p
oin
t
A
.
a
It
is
assumed
that
at
some
p
oin
t
t
jean
catc
hes
the
p
om-p
om
in
A
.
Jean
ma
y
already
ha
v
e
passed
a
n
um-
b
er
of
times
in
A
without
finding
the
p
omp
on
there.
A
t
time
t
,
w
e
note
y
the
n
um
b
er
of
turns
made
since
its
first
passage
in
A
and
x
the
n
um
b
er
of
turns
made
b
y
the
p
omp
on.
Sho
w
that
(
x
;
y
)
is
a
solution
of
the
equation
(
E
)
from
question
1.
b
Jean
has
paid
for
2
min
utes
;
will
he
ha
v
e
time
to
catc
h
the
p
om-p
om?
c
Sho
w,
in
fact,
that
it
is
only
p
ossible
to
catc
h
the
p
om-
p
om
at
p
oin
t
A
.
d
Jean
no
w
starts
from
p
oin
t
E
.
Will
he
ha
v
e
time
to
catc
h
the
p
om-p
om
in
A
b
efore
the
t
w
o
min
utes.
E.6249
P
art
A
The
aim
of
this
part
is
to
demonstrate
that
the
set
of
prime
in
tegers
is
infinite
b
y
reasoning
b
y
the
absurd.
1
It
is
assumed
that
there
exists
a
finite
n
um
b
er
of
prime
in
tegers
denoted
p
1
,
p
2
,
.
.
.
,
p
n
.
Consider
the
in
teger
E
pro
duct
of
all
prime
in
tegers
aug-
men
ted
b
y
1
:
E
=
p
1
×
p
2
×
·
·
·
×
p
n
+
1
Sho
w
that
E
is
an
in
teger
greater
than
or
equal
to
2
,
and
that
E
is
prime
with
eac
h
of
the
in
tegers
p
1
,
p
2
,
.
.
.
,
p
n
.
2
Using
the
fact
that
E
admits
a
prime
divisor,
conclude.
P
art
B
F
or
an
y
natural
n
um
b
er
k
2
,
w
e
p
ose
:
M
k
=
2
k
−
1
.
W
e
sa
y
that
M
k
is
the
k
-th
Mersenne
n
um
b
er.
1
a
Cop
y
and
complete
the
follo
wing
table,
whic
h
giv
es
some
v
alues
of
M
k
:
k
2
3
4
5
6
7
8
9
10
M
k
b
F
rom
the
previous
table,
if
k
is
a
prime
in
teger,
can
w
e
conjecture
that
the
in
teger
M
k
is
prime?
2
Let
p
and
q
b
e
t
w
o
non-zero
natural
n
um
b
ers.
a
Justify
the
equalit
y
:
1
+
2
p
+
2
p
2
+
·
·
·
+
2
p
q
−
1
=
2
p
q
−
1
2
p
−
1
b
Deduce
that
2
p
·
q
−
1
is
divisible
b
y
2
p
−
1
.
c
Deduce
that
if
an
in
teger
k
greater
than
or
equal
to
2
is
not
prime,
then
neither
is
M
k
.
3
a
Pro
v
e
that
Mersenne’s
n
um
b
er
M
11
is
not
prime.
b
What
can
w
e
deduce
ab
out
the
conjecture
in
question
1
b
?
P
art
C
The
Lucas-Lehmer
test
is
used
to
determine
whether
a
giv
en
Mersenne
n
um
b
er
is
prime.
This
test
uses
the
n
umerical
se-
quence
u
n
defined
b
y
u
0
=
4
and
for
an
y
natural
n
um
b
er
n
:
u
n
+1
=
u
n
2
−
2
If
n
is
a
natural
n
um
b
er
greater
than
or
equal
to
2
,
the
test
asserts
that
the
in
teger
M
n
is
prime
if,
and
only
if,
u
n
−
2
≡
0
(
mo
d.
M
n
)
.
This
prop
ert
y
is
admitted
in
the
sequel.
1
Use
the
Lucas-Lehmer
test
to
c
hec
k
that
the
Mersenne
n
um
b
er
M
5
is
prime.
2
The
function
of
the
follo
wing
algorithm
tak
es
as
argu-
men
t
an
in
teger
n
greater
than
or
equal
to
3
and
m
ust
return
1
if
the
Mersenne
n
um
b
er
M
n
is
prime
and
0
oth-
erwise,
using
the
Lucas-Lehmer
test.
h
ttps:/
/c
hingmath.fr
chapExoCorrec/1604
sacados/1604
Polynesie Juin 2006 5 pionts
chapExoCorrec/3133
sacados/3133
A
B
C
D
E
F
G
H
chapExoCorrec/6249
sacados/6249
Asie Juin 2014
Function
f(n)
u
←
4
M
←
...
For
i
ranging
from
1
to
...
u
←
...
End
For
If
M
divides
u
Then
Return
......
Otherwise
Return
......
End
If
Cop
y
and
complete
the
function
co
de
f
so
that
it
satisfies
the
desired
condition.
E.3552
P
art
I
Let
x
b
e
a
real
n
um
b
er.
1
Sho
w
that
:
x
4
+4
=
x
2
+2
2
−
4
·
x
2
.
2
Deduce
that
x
4
+4
can
b
e
written
as
the
pro
duct
of
t
w
o
trinomials
with
in
teger
co
efficien
ts.
P
art
I
I
Let
n
b
e
a
natural
n
um
b
er
greater
than
or
equal
to
2
.
Consider
the
in
tegers
:
A
=
n
2
−
2
n
+2
;
B
=
n
2
+2
n
+2
and
d
their
P
GC
D
.
1
Sho
w
that
n
4
+4
is
not
prime.
2
Sho
w
that,
an
y
divisor
of
A
that
divides
n
,
divides
2
.
3
Sho
w
that,
an
y
common
divisor
of
A
and
B
,
divides
4
n
.
4
In
this
question,
it
is
assumed
that
n
is
o
dd.
a
Sho
w
that
A
and
B
are
o
dd.
Deduce
that
d
is
o
dd.
b
Sho
w
that
d
divides
n
.
c
Deduce
that
d
divides
2
,
then
that
A
and
B
are
prime
to
eac
h
other.
5
It
is
no
w
assumed
that
n
is
ev
en.
a
Sho
w
that
4
do
es
not
divide
n
2
−
2
n
+2
.
b
Sho
w
that
d
is
of
the
form
d
=
2
·
p
,
où
p
is
o
dd.
c
Sho
w
that
p
divides
n
.
Deduce
that
d
=
2
.
(This
may
b
e
b
ase
d
on
the
demonstr
ation
use
d
in
question
4
)
.
E.6928
F
or
an
y
non-zero
natural
n
um
b
er
n
,
w
e
call
S
(
n
)
the
n
um
b
er
equal
to
the
sum
of
the
p
ositiv
e
divisors
of
n
.
1
Chec
k
that
S
(6)
=
12
and
calculate
S
(7)
.
2
a
Sho
w
that,
for
an
y
natural
n
um
b
er
n
greater
than
or
equal
to
2
:
S
(
n
)
1+
n
b
What
are
the
natural
n
um
b
ers
n
suc
h
that
S
(
n
)
=
1+
n
?
3
It
is
assumed
in
this
question
that
n
is
written
p
×
q
où
p
and
q
are
distinct
prime
in
tegers.
a
Sho
w
that
:
S
(
n
)
=
1+
p
1+
q
.
b
Consider
the
follo
wing
prop
osition
:
ˇ
F
or
all
distinct
nonzero
natural
n
um
b
ers
n
and
m
,
S
n
×
m
=
S
n
×
S
m
ı
Is
this
prop
osition
true
or
false?
Justify
.
4
It
is
assumed
in
this
question
that
the
in
teger
n
is
writ-
ten
p
k
,
où
p
is
a
prime
in
teger
and
k
a
non-zero
natural
n
um
b
er.
a
What
are
the
divisors
of
n
?
b
Deduce
that
:
S
(
n
)
=
1
−
p
k
+1
1
−
p
.
5
It
is
assumed
in
this
question
that
n
is
written
p
13
×
q
7
,
où
p
and
q
are
distinct
prime
in
tegers.
a
Let
m
b
e
a
natural
n
um
b
er.
Sho
w
that
m
divides
n
if,
and
only
if,
there
exist
t
w
o
in
tegers
s
and
t
with
0
s
13
and
0
t
7
suc
h
that
m
=
p
s
×
q
t
.
b
Sho
w
that
:
S
(
n
)
=
1
−
p
14
1
−
p
×
1
−
q
8
1
−
q
h
ttps:/
/c
hingmath.fr
chapExoCorrec/3552
sacados/3552
chapExoCorrec/6928
sacados/6928
E.6946
F
or
an
y
pair
of
non-zero
relativ
e
in
tegers
(
a
;
b
)
,
note
pgcd
(
a
;
b
)
the
greatest
common
divisor
of
a
and
b
.
The
plane
is
pro
vided
with
a
reference
frame
O
;
−
→
i
;
−
→
j
.
1
Example.
Let
Δ
1
b
e
the
straigh
t
line
with
equation
:
y
=
5
4
·
x
−
2
3
a
Sho
w
that
if
(
x
;
y
)
is
a
pair
of
relativ
e
in
tegers
then
the
in
teger
15
·
x
−
12
·
y
is
divisible
b
y
3
.
b
Is
there
at
least
one
p
oin
t
on
the
line
Δ
1
whose
co
or-
dinates
are
t
w
o
relativ
e
in
tegers?
Justify
.
Generalization
:
No
w
consider
a
straigh
t
line
Δ
with
equation
:
y
=
m
n
·
x
−
p
q
où
m
,
n
,
p
and
q
are
non-zero
relativ
e
in
tegers
suc
h
that
:
pgcd
(
m
;
n
)
=
pgcd
(
p
;
q
)
=
1
Th
us,
the
co
efficien
ts
of
the
equation
(
E
)
are
irreducible
frac-
tions
and
w
e
sa
y
that
Δ
is
a
rational
line.
The
aim
of
the
exercise
is
to
determine
a
necessary
and
suffi-
cien
t
condition
on
m
,
n
,
p
and
q
so
that
a
rational
line
Δ
has
at
least
one
p
oin
t
whose
co
ordinates
are
t
w
o
relativ
e
in
tegers.
2
It
is
assumed
here
that
the
line
Δ
has
a
p
oin
t
with
co
or-
dinates
x
0
;
y
0
où
x
0
and
y
0
are
relativ
e
in
tegers.
a
Noting
that
the
n
um
b
er
n
·
y
0
−
m
·
x
0
is
a
relativ
e
in
te-
ger,
demonstrate
that
q
divides
the
pro
duct
n
·
p
.
b
Deduce
that
q
divides
n
.
3
Recipro
cally
,
w
e
assume
that
q
divides
n
,
and
w
e
wish
to
find
a
pair
x
0
;
y
0
of
relativ
e
in
tegers
suc
h
that
:
y
0
=
m
n
·
x
0
−
p
q
.
a
W
e
p
ose
n
=
q
·
r
,
où
r
is
a
non-zero
relativ
e
in
teger.
Sho
w
that
w
e
can
find
t
w
o
relativ
e
in
tegers
u
and
v
suc
h
that
:
q
·
r
·
u
−
m
·
v
=
1
.
b
Deduce
that
there
exists
a
pair
(
x
0
;
y
0
)
of
relativ
e
in-
tegers
suc
h
that
:
y
0
=
m
n
·
x
0
−
p
q
4
Let
Δ
b
e
the
straigh
t
line
of
equation
y
=
3
8
·
x
−
7
4
.
Do
es
this
line
ha
v
e
a
p
oin
t
whose
co
ordinates
are
relativ
e
in-
tegers?
Justify
.
5
Consider
the
function
f
of
an
algorithm
taking
as
argu-
men
ts
the
in
tegers
M
,
N
,
P
and
Q
.
F
urthermore,
w
e
assume
that
the
argumen
ts
passed
when
calling
the
f
function
v
erify
:
pgcd
(
M
;
N
)
=
pgcd
(
P
;
Q
)
=
1
Function
f(M,N,P,Q)
If
Q
divides
N
Then
X
←
0
As
long
as
M
N
·
X
−
P
Q
is
not
entier
and
−
M
N
·
X
−
P
Q
is
not
entier
X
←
X+1
End
As
long
as
If
M
N
X
−
P
Q
is
integer
Then
Renvoyer
X
;
M
N
·
X
−
P
Q
Otherwise
Renvoyer
−
X
;
M
N
·
X
−
P
Q
End
If
Otherwise
Return
"No
solution
End
if
a
Justify
that
the
call
to
the
function
f
terminates
for
all
v
alues
passed
as
argumen
ts
to
M
,
N
,
P
,
Q
,
non-zero
in
tegers
v
erifying
:
pgcd
(
M
;
N
)
=
pgcd
(
P
;
Q
)
=
1
.
b
What
do
es
it
ac
hiev
e?
E.3551
Let
p
b
e
a
giv
en
prime
in
teger.
W
e
prop
ose
to
study
the
exitence
of
couples
(
x
;
y
)
of
strictly
p
ositiv
e
natural
in
tegers
v
erifying
the
equation
:
(
E
)
:
x
2
+
y
2
=
p
2
1
W
e
p
ose
p
=
2
.
Sho
w
that
the
equation
(
E
)
is
without
solution.
W
e
no
w
assume
p
=
2
and
that
the
couple
(
x
;
y
)
is
solution
of
the
equation
(
E
)
.
2
The
aim
of
this
question
is
to
pro
v
e
that
x
and
y
are
prime
to
eac
h
other.
a
Sho
w
that
x
and
y
are
of
differen
t
parities.
b
Sho
w
that
x
and
y
are
not
divisible
b
y
p
.
c
Deduce
that
x
and
y
are
prime
to
eac
h
other.
3
It
is
no
w
assumed
that
p
is
a
sum
of
t
w
o
non-zero
squares,
i.e.
:
p
=
u
2
+
v
2
où
u
and
v
are
t
w
o
strictly
p
ositiv
e
natu-
ral
n
um
b
ers.
a
V
erify
that
then
the
couple
(
|
u
2
−
v
2
|
;
2
·
u
·
v
)
is
solution
of
equation
(
E
)
.
b
Giv
e
a
solution
of
the
equation
(
E
)
when
p
=
5
then
when
p
=
13
.
4
Finally
,
w
e
prop
ose
to
c
hec
k
on
t
w
o
examples,
that
the
equation
(
E
)
is
imp
ossible
when
p
is
not
the
sum
of
t
w
o
squares.
a
Are
p
=
3
and
p
=
7
the
sum
of
t
w
o
squares?
b
Demonstrate
that
the
equations
x
2
+
y
2
=
9
and
x
2
+
y
2
=
49
admit
no
solution
in
strictly
p
ositiv
e
natural
n
um
b
ers.
h
ttps:/
/c
hingmath.fr
chapExoCorrec/6946
sacados/6946
chapExoCorrec/3551
sacados/3551
E.5862
W
e
note
E
the
set
of
t
w
en
t
y-sev
en
in
tegers
b
et
w
een
0
and
26
.
W
e
note
A
the
set
whose
elemen
ts
are
the
t
w
en
t
y-six
letters
of
the
alphab
et
and
a
separator
b
et
w
een
t
w
o
w
ords,
noted
ˇ
?
ı
considered
as
a
c
haracter.
T
o
co
de
the
elemen
ts
of
A
,
w
e
pro
ceed
as
follo
ws
:
Firstly
:
eac
h
letter
of
the
alphab
et,
arranged
alphab
eti-
cally
,
is
asso
ciated
with
a
natural
n
um
b
er
b
et
w
een
0
and
25
,
arranged
in
ascending
order.
W
e
therefore
ha
v
e
:
a
↦−
→
0
;
b
↦−
→
1
;
.
.
.
;
z
↦−
→
25
.
The
separator
ˇ
?
ı
is
asso
ciated
with
the
in
teger
26
.
a
b
c
d
e
f
g
h
i
j
k
l
m
n
0
1
2
3
4
5
6
7
8
9
10
11
12
13
o
p
q
r
s
t
u
v
w
x
y
z
?
14
15
16
17
18
19
20
21
22
23
24
25
26
W
e
sa
y
that
a
has
rank
0
,
b
has
rank
1
,.
.
.
,
z
has
rank
25
and
the
separator
ˇ
?
ı
has
rank
26
.
Secondly
:
to
eac
h
elemen
t
x
of
E
,
the
application
g
as-
so
ciates
the
remainder
of
the
Euclidean
division
of
4
x
+
3
b
y
27
.
Note
that,
for
an
y
x
of
E
,
g
(
x
)
b
elongs
to
E
.
Thirdly
:
the
initial
c
haracter
is
then
replaced
b
y
the
rank
c
haracter
g
(
x
)
.
Example
:
s
↦−
→
18
;
g
(18)
=
21
;
21
↦−
→
v
.
So
the
letter
s
is
replaced
during
co
ding
b
y
the
letter
v
.
1
Find
all
in
tegers
x
of
E
suc
h
that
g
(
x
)
=
x
,
i.e.
in
v
arian
t
b
y
the
application
g
.
Deduce
all
the
in
v
arian
t
c
haracters
in
this
enco
ding.
2
Sho
w
that,
for
an
y
natural
n
um
b
er
x
b
elonging
to
E
and
an
y
natural
n
um
b
er
y
b
elonging
to
E
:
If
y
≡
4
x
+3
(
mo
d.
27)
then
x
≡
7
y
+6
(
mo
d.
27)
Deduce
that
t
w
o
distinct
c
haracters
are
enco
ded
b
y
t
w
o
distinct
c
haracters.
3
Suggest
a
deco
ding
metho
d.
4
Deco
de
the
w
ord
ˇ
v
f
v
ı.
E.6903
The
natural
in
tegers
1
,
11
,
111
,
1111
.
.
.
are
rep-units.
Natural
in
tegers
written
only
with
1
are
so
called.
F
or
an
y
non-zero
natural
n
um
b
er
p
,
note
N
p
the
rep-unit
writ-
ten
with
p
times
the
digit
1
:
N
p
=
11
:
:
:
1
p
rép
étitions
du
c
hiffre
1
=
k
=
p
−
1
k
=0
10
k
Throughout
the
exercise,
p
denotes
a
non-zero
natural
n
um-
b
er.
The
aim
of
this
exercise
is
to
study
some
prop
erties
of
rep-
units.
P
art
A
:
divisibilit
y
of
rep-units
in
some
sp
ecial
cases
1
Sho
w
that
N
p
is
divisible
neither
b
y
2
nor
b
y
5
.
2
In
this
question,
w
e
study
the
divisibilit
y
of
N
p
b
y
3
.
a
Pro
v
e
that,
for
an
y
natural
n
um
b
er
j
:
10
j
≡
1
(
mo
d.
3)
b
Deduce
that
N
p
≡
p
(
mo
d.
3)
.
c
Determine
a
necessary
and
sufficien
t
condition
for
the
rep-unit
N
p
to
b
e
divisible
b
y
3
.
3
In
this
question,
w
e
study
the
divisibilit
y
N
p
b
y
7
.
a
Cop
y
and
complete
the
congruence
table
b
elo
w,
où
a
is
the
only
relativ
e
in
teger
b
elonging
to
:
−
3
;
−
2
;
−
1
;
0
;
1
;
2
;
3
suc
h
as
:
10
m
≡
a
(
mo
d.
7)
No
justification
is
required
.
m
0
1
2
3
4
5
6
a
b
Let
p
b
e
a
non-zero
natural
n
um
b
er.
Sho
w
that
10
p
≡
1
(
mo
d.
7)
if,
and
only
if,
p
is
a
m
ul-
tiple
of
6
.
The
Euclidean
division
of
p
b
y
6
.
can
b
e
used
c
Justify
that,
for
an
y
non-zero
natural
n
um
b
er
p
:
N
p
=
10
p
−
1
9
d
Demonstrate
that
ˇ
7
divides
N
p
ı
is
equiv
alen
t
to
ˇ
7
divides
9
·
N
p
ı.
e
Deduce
that
N
p
is
divisible
b
y
7
if,
and
only
if,
p
is
a
m
ultiple
of
6
.
P
art
B
:
a
rep-unit
strictly
greater
than
1
is
nev
er
a
p
erfect
square
1
Let
n
b
e
a
natural
n
um
b
er
greater
than
or
equal
to
2
.
It
is
assumed
that
the
decimal
writing
of
n
2
ends
with
the
digit
1
,
i.e.
n
2
≡
1
(
mo
d.
10)
a
Cop
y
and
complete
the
congruence
table
b
elo
w
:
n
≡
:
:
:
[10]
0
1
2
3
4
5
6
7
8
9
n
2
≡
:
:
:
[10]
b
Deduce
that
there
exists
a
natural
in
teger
m
suc
h
that
:
n
=
10
·
m
+
1
or
n
=
10
·
m
−
1
c
Conclude
that
:
n
2
≡
1
(
mo
d.
20)
2
Let
p
b
e
a
natural
n
um
b
er
greater
than
or
equal
to
2
.
What
is
the
remainder
of
the
Euclidean
division
of
N
p
h
ttps:/
/c
hingmath.fr
chapExoCorrec/5862
sacados/5862
chapExoCorrec/6903
sacados/6903
b
y
20
?
3
Deduce
that,
for
p
natural
in
teger
greater
than
or
equal
to
2
,
the
rep-unit
N
p
is
not
the
square
of
an
in
teger.
E.8134
Eac
h
letter
of
the
alphab
et
is
as-
so
ciated
with
an
in
teger
x
b
et
w
een
0
and
25
as
sho
wn
in
the
table
b
elo
w
:
Lettre
A
B
C
D
E
F
G
H
I
J
K
L
M
x
0
1
2
3
4
5
6
7
8
9
10
11
12
Lettre
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
x
13
14
15
16
17
18
19
20
21
22
23
24
25
The
ˇ
RABIN
ı
cipher
is
an
asymmetric
encryption
device
in-
v
en
ted
in
1979
b
y
computer
scien
tist
Mic
hael
Rabin.
Alice
w
an
ts
to
comm
unicate
securely
using
this
cryptosystem.
She
c
ho
oses
t
w
o
distinct
n
um
b
ers
p
and
q
.
This
pair
of
n
um-
b
ers
is
her
priv
ate
k
ey
,
whic
h
she
k
eeps
secret.
She
then
calculates
n
=
p
×
q
and
c
ho
oses
a
natural
n
um
b
er
B
suc
h
that
0
B
n
−
1
.
If
Bob
w
an
ts
to
send
a
secret
message
to
Alice,
he
co
des
it
letter
b
y
letter.
The
enco
ding
of
a
letter
represen
ted
b
y
the
in
teger
x
is
the
n
um
b
er
y
suc
h
that
:
y
≡
x
x
+
B
(
mo
d.
n
)
with
0
y
n
Throughout
the
exercise,
w
e
tak
e
p
=
3
,
q
=
11
so
n
=
p
×
q
=
33
and
B
=
13
.
P
art
A
:
Encryption
Bob
w
an
ts
to
send
the
w
ord
ˇ
NO
ı
to
Alice.
1
Sho
w
that
Bob
co
des
the
letter
ˇ
N
ı
with
the
n
um
b
er
8
.
2
Determine
the
n
um
b
er
that
enco
des
the
letter
ˇ
O
ı.
P
art
B
:
Decryption
Alice
has
receiv
ed
an
encrypted
message
that
b
egins
with
the
n
um
b
er
3
.
T
o
deco
de
this
first
n
um
b
er,
she
needs
to
determine
the
in
te-
ger
x
suc
h
that
:
x
x
+3
≡
3
(
mo
d.
33)
0
x
<
26
1
Sho
w
that
x
·
x
+13
≡
3
(
mo
d.
33)
is
equiv
alen
t
to
:
x
+
23
2
≡
4
(
mo
d.
33)
.
2
a
Sho
w
that
if
x
+23
2
≡
4
(
mo
d.
33)
then
the
system
of
equations
x
+
23
2
≡
4
(
mo
d.
3)
x
+
23
2
≡
4
(
mo
d.
11)
is
v
erified.
b
Recipro
cally
,
sho
w
that
if
x
+
23
2
≡
4
(
mo
d.
3)
x
+
23
2
≡
4
(
mo
d.
11)
alors
x
+23
2
≡
4
(
mo
d.
33)
c
Deduce
that
:
x
·
x
+13
≡
3
(
mo
d.
33)
⇐
⇒
x
+23
2
≡
1
(
mo
d.
3)
x
+23
2
≡
4
(
mo
d.
11)
3
a
Determine
the
natural
n
um
b
ers
a
suc
h
that
0
a
<
3
and
a
2
≡
1
(
mo
d.
3)
b
Determine
the
natural
n
um
b
ers
b
suc
h
that
0
b
<
11
and
b
2
≡
4
(
mo
d.
11)
4
a
Deduce
that
x
·
x
+13
≡
3
(
mo
d.
33)
is
equiv
alen
t
to
the
follo
wing
four
systems
:
x
≡
2
(
mo
d.
3)
x
≡
8
(
mo
d.
11)
or
x
≡
0
(
mo
d.
3)
x
≡
1
(
mo
d.
11)
ou
x
≡
2
(
mo
d.
3)
x
≡
1
(
mo
d.
11)
or
x
≡
0
(
mo
d.
3)
x
≡
8
(
mo
d.
11)
b
W
e
admit
that
eac
h
of
these
systems
admits
a
single
in
teger
solution
x
suc
h
that
0
x
<
33
.
Determine,
without
justification,
eac
h
of
these
solu-
tions.
5
Complete
the
algorithm
b
elo
w
so
that
it
displa
ys
the
four
solutions
found
in
the
previous
question.
Pour...allant
de...à...
If
the
remainder
of
the
division
de...par...est
equals...then
Display
...
End
If
End
For
6
Can
Alice
find
out
the
first
letter
of
the
message
sen
t
b
y
Bob?
Can
ˇ
cipher’s
RABIN
ı
b
e
used
to
deco
de
a
message
letter
b
y
letter?
E.8140
The
aim
of
this
exercise
is
to
con-
sider
a
metho
d
of
public-k
ey
encryption
of
digital
information,
called
the
RSA
system,
in
honor
of
mathematicians
Ronald
Riv
est,
A
di
Shamir
and
Leonard
A
dleman,
who
in
v
en
ted
this
encryption
metho
d
in
1977
and
published
it
in
1978
.
Questions
1
and
2
are
preparatory
questions,
question
3
addresses
encryption,
question
4
decryption.
1
This
question
considers
calculating
the
remainder
in
Eu-
clidean
division
b
y
55
of
certain
p
o
w
ers
of
the
in
teger
8
.
a
Chec
k
that
8
7
≡
2
(
mo
d.
55)
.
Deduce
the
remainder
in
Euclidean
division
b
y
55
of
the
n
um
b
er
8
21
.
b
V
erify
that
8
2
≡
9
(
mo
d.
55)
,
then
deduce
from
ques-
tion
a
the
remainder
in
Euclidean
division
b
y
55
of
8
23
.
2
In
this
question,
consider
the
equation
:
(
E
)
23
·
x
−
40
·
y
=
1
,
whose
solutions
are
couples
(
x
;
y
)
of
relativ
e
in
tegers.
a
Justify
the
fact
that
the
equation
(
E
)
admits
at
least
one
solution
pair.
b
Giv
e
a
couple,
particular
solution
of
the
equation
(
E
)
.
c
Determine
all
pairs
of
relativ
e
in
tegers
solution
of
equa-
tion
(
E
)
.
d
Deduce
that
there
exists
a
unique
in
teger
d
v
erifying
the
conditions
:
0
d
<
40
et
23
·
d
≡
1
(
mo
d.
40)
.
3
Encryption
in
the
RSA
system
A
p
erson
A
c
ho
oses
t
w
o
prime
n
um
b
ers
p
and
q
,
then
cal-
culates
the
pro
ducts
N
=
p
·
q
and
n
=
p
−
1
q
−
1
.
She
also
c
ho
oses
a
natural
n
um
b
er
c
prime
with
n
.
The
p
erson
A
publishes
the
pair
(
N
;
c
)
,
whic
h
is
a
public
k
ey
allo
wing
an
y
one
to
send
him
an
encrypted
n
um
b
er.
Messages
are
digitized
and
transformed
in
to
a
sequence
of
in
tegers
b
et
w
een
0
and
n
−
1
.
T
o
encrypt
an
in
teger
a
from
this
sequence,
pro
ceed
as
follo
ws
:
calculate
the
remainder
b
in
the
Euclidean
divi-
sion
b
y
N
of
the
n
um
b
er
a
c
,
and
the
encrypted
n
um
b
er
is
the
in
teger
b
.
In
practice,
this
metho
d
is
secure
if
the
p
erson
A
c
ho
oses
h
ttps:/
/c
hingmath.fr
sacados/8134
sacados/8140
v
ery
large
prime
n
um
b
ers
p
and
q
,
written
with
sev
eral
tens
of
digits.
W
e’ll
consider
it
here
with
simpler
n
um
b
ers
:
p
=
5
et
q
=
11
.
The
p
erson
A
also
c
ho
oses
c
=
23
.
a
Calculate
the
n
um
b
ers
N
and
n
,
then
justify
that
the
v
alue
of
c
v
erifies
the
desired
condition.
b
A
sender
wishes
to
send
to
p
erson
A
the
n
um
b
er
a
=
8
.
Determine
the
v
alue
of
the
encrypted
n
um
b
er
b
.
4
Decryption
in
the
RSA
system
The
p
erson
A
first
calculates
the
unique
natural
in
teger
d
v
erifying
the
conditions
:
0
d
<
n
et
c
·
d
≡
1
(
mo
d.
n
)
.
She
k
eeps
secret
this
n
um
b
er
d
whic
h
allo
ws
her,
and
her
alone,
to
decrypt
the
n
um
b
ers
sen
t
to
her
encrypted
with
her
public
k
ey
.
T
o
decrypt
an
encrypted
n
um
b
er
b
,
the
p
erson
A
cal-
culates
the
remainder
a
in
the
Euclidean
division
b
y
N
of
the
n
um
b
er
b
d
,
and
the
plain
text
n
um
b
er
-
i.e.
the
n
um
b
er
b
efore
encryption
-
is
the
n
um
b
er
a
.
W
e
admit
the
existence
and
uniqueness
of
the
in
teger
d
,
and
the
fact
that
decryption
w
orks.
The
n
um
b
ers
c
hosen
b
y
A
are
still
p
=
5
,
q
=
11
and
c
=
23
.
a
What
is
the
v
alue
of
d
?
b
Applying
the
decryption
rule,
find
the
plain
text
n
um-
b
er
when
the
encrypted
n
um
b
er
is
b
=
17
.
E.8149
South
America
2018
h
ttps:/
/c
hingmath.fr
sacados/8149
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