Petites congruences

par **ArtyB** » 04 Déc 2015, 22:32

Bonjour,

Voici quelques questions de congruences sur lesquelles je bloque:

1) Déterminer la congruence de:

modulo 7
J'ai remarqué la forme assez particulière de l'expression:

mais n'ai aucune idée de la démarche à suivre pour résoudre cette question, j'ai beau avoir lu des cours sur les congruences je ne vois rien qui puisse m'être utile. Je veux bien des indices

2) Enoncer le théorème d'Euler et déterminer la congruence de

modulo 18.
Le théorème d'Euler énonce que pour n un entier positif et a un entier premier avec n, on a:

.
Mais comment calculer l'indicatrice d'Euler d'un nombre ?

3)Déterminer l'ensemble des entiers relatifs congrus à 1 modulo 31 et 2 modulo 53.
Pour celle-ci je n'ai vraiment aucune idée, pas la moindre intuition, si vous avez des idées/conseils je suis preneur !

par **Ben314** » 04 Déc 2015, 23:03

Salut,
Pour la 1), tu commence par utiliser le fait que, si

alors

pour tout entier n pour diminuer la taille des nombre "sous" les exposants (je sais pas comment on dit...)
Ensuite, soit tu utilise le théorème d'Euler pour réduire les exposants, soit tu calcule les puissances 1, puis 2, puis 3, etc (modulo 7) jusqu'à ce que tu comprenne la logique.
Et sinon, je ne pense pas que la forme particulière a^b+b^a puisse servir à grand chose ici.

Pour la 2), ça me semble quand même très étrange que tu ait vu le théorème d'Euler sans avoir vu comment on calcule l'indicatrice d'Euler : tu as pas un cours là dessus ?
Normalement, je pense que tu devrait avoir vu que :
- Si a et b sont premiers entre eux alors

- Si p est un nombre premier et n un entier alors

Et avec ça, on peut calculer

pour tout entier n.

Pour la 3, tu cherche les solutions du système d'équations :

donc de

et ça je pense que tu doit savoir le résoudre.

EDIT : pour l'indicatrice d'Euler, peut-être que pour le moment tu as juste vu que c'était le nombre d'entiers entre 1 et n qui sont premiers avec n et ç'est suffisant pour calculer

(18 c'est pas trop "gros"...)

par **remullen2000** » 04 Déc 2015, 23:22

Bonsoir,

1) 1820 est congru à 0 modulo 7 et 25 est congru à 4.

Il faut connaître les propriétés de somme, de produit et de puissance de congruence.

2) un indice: ici n=18 et on va prendre a=7!

3) Par exemple tu peux traduire la congruence de cette manière:

x est congru à 1 modulo 31 signifie que.......... x=31k+1.... De même avec l'autre et tu aura une équation diophantienne à résoudre.

EDIT: désolé je n'avais pas vu le post de BEN

par **aymanemaysae** » 04 Déc 2015, 23:30

En marge de la démarche que M. Ben à proposée, j'ose attirer votre attention sur le fait que:
1) 1820 = 260 x 7.
2) 1818 = 3 x 606.
3) 25^3 est équivalent à 1 [7].

Je demande aussi pardon à M. remullen 2000, qui a déjà posté les idées auxquelles j'ai fait allusion dans mon post.

par **ArtyB** » 04 Déc 2015, 23:36

Bonjour,

Merci de ta réponse.
Pour la 1 j'avais ça:

donc

Et

Donc

Mais après j'étais un peu coincé, est-ce que si a congrue à b modulo d et c congrue à e modulo d alors a+c congrue à d+e modulo c ?

Je n'ai pas toutes ces propriétés sur le théorème d'Euler je n'ai en effet vu que c'était le nombre d'entiers entre 1 et n premiers avec n. Je ne sais pas du tout comment la calculer et ça m'embête pas mal. Du coup je viens d'aller regarder un peut tout ça et c'est chouette en effet et je peux calculer l'indicatrice d'Euler:

où p parcourt l'ensemble des diviseurs premiers de n.
Et comment suis je sensé l'utiliser ? Ca ne m'a pas l'air très intuitif à utiliser.

Pour la 2) maintenant j'ai les formules et propriétés mais comment cela permet il de résoudre le problème ?
On a

donc

mais ensuite ?

Pour la 3) Yep, par Euclide ?

EDIT: Je n'avais vu que le post de Ben

par **aymanemaysae** » 04 Déc 2015, 23:46

Et 25

4(7)
Donc 25^{1820}

(7)

Veuillez considérer d'abord que

1[7],et 1818=3*606.

par **Ben314** » 04 Déc 2015, 23:50

- Oui : si

et

alors

et aussi

: c'est la base des congruences et ça se démontre aisément.

- Si tu as uniquement vu que phi(n) est le nombre d'entier entre 1 et n premier avec n, je pense que ça serait mieux que tu l'utilise pour calculer phi(18) plutôt qu'une formule que tu n'as as encore vue : c'est quand même pas super long de dresser la liste des entiers entre 1 et 18 premiers avec 18. (évidement, le jour où il faudra calculer phi(3572), ça sera pas la bonne méthode, mais pour 18, faut pas déconner...)

- Vu que

, ça vaut combien

modulo 18 ?
et

(n entier) modulo 18 ?

par **remullen2000** » 04 Déc 2015, 23:55

Attention il faut prendre a=7 et non a=2 car il n est pas premier avec 18!

par **Ben314** » 04 Déc 2015, 23:59

Effectivement : j'ai bêtement recopié la faute de frappe de ArtyB dans son post juste au dessus...

par **ArtyB** » 05 Déc 2015, 00:51

1)Merci de votre aide, je crois avoir trouvé:
Du coup du fait que:

i.e.

et

i.e.

On a:

Or

D'où:

c'est ça ?

2)Oui 7 et non deux, toutes mes excuses.
Donc on a:

c'est bien ça ?

par **nodjim** » 05 Déc 2015, 07:56

ArtyB, si on te demande un résultat modulo 7, c'est à dire le reste d'une division par 7, ton résultat est nécessairement compris entre 0 et 6.

par **aymanemaysae** » 05 Déc 2015, 13:44

par **aymanemaysae** » 05 Déc 2015, 13:47

par **ArtyB** » 05 Déc 2015, 18:03

C'est aussi ce que j'ai obtenu pour toutes les questions cette nuit.

Petites congruences

Petites congruences

Qui est en ligne