Crypto_sage

[pic 1]

Sommaire

Exercice 1:        3

Solution:        3

Exercice 2:        3

Solution:        3

Exercice 3:        4

Solution:        4

Exercice 1:

Montrer que la relation de congruence est une relation d'équivalence.

Solution:

 On appelle relation d'équivalence dans toute relation binaire qui est réflexive, symétrique et transitive

Soit la relation suivante :

                a-b un multiple de n => a ≡ b(mod n)

1) cette relation est réflexive.

         En effet pour tout a ∈ Z a-a = 0 est un multiple de n.

2) Cette relation est symétrique

        Car si a-b est un multiple de n alors donc son opposé b-a est lui aussi         un multiple de n.

3) Cette relation est transitive.

        Si il existe q ∈ Z tel que a-b = nq et qu'il existe k ∈ Z tel que b-c = nk alors a-c=nn(q+k) => n divise a-c alors a ≡ c(mod n)

D'ou la relation de congruence est une relation d'équivalence.

Exercice 2:

Faite la preuve du théorème de pgcd du cours.

Solution:

Si c|a => a=kc avec k∈Z

Si c|b => b=k'c avec k'∈Z

on alors au + bv = kcu + k'cv

                                    = c(ku + k'v)

avec ku+k'v ∈ Z donc c|au+bv, si p = au+bv alors c|p qui ne rien d'autre que le pgcd(a,b).

Exercice 3:

Si a ≡ a'(mod n) et b ≡ b'(mod n) alors a+b ≡ a'+b'(mod n) et ab ≡a' b'(mod n)

Demontrer.

Solution:

a ≡ a'(mod n) => a-a' = nk  (1)

b ≡ b'(mod n) => b-b' = nk' (2)

(1)+(2) = (a+b) - (a'-b') = n(k+k') d'ou a+b ≡ a'+b'(mod n).

(1)(2) = ab = (a'+nq)(b'+nk)

                  = a'b' +n(a'k+qb'+nqk)

ab-a'b' = n(a'k+qb'+nqk) d'ou ab ≡a' b'(mod n)

...