L305, exercices illustrant emploi nb premiers

Le theoreme des restes chinois est tres utilise en calcul exact, et toujours avec un nombre premier et un produit de nombres premiers, il me semble donc parfaitement dans le sujet. Par exemple pour calculer un determinant de matrice a coefficients entiers en utilisant des determinants modulo un nombre suffisant de nombres premiers.

Fonction d'Euler

Le théorème des restes chinois me semble un peu hors-sujet car il nécessite des nombres premiers entre eux, des premiers distincts ça fonctionne mais ça me semble juste pour illustrer l’emploi de nombres premiers.
Je trouve cette épreuve sur dossier difficile car il est facile de tomber dans le hors-sujet, même de bonne foi.

@nicolas.patrois: pas du tout d'accord avec vous, l'exemple que je donnais, un exercice sur le calcul du determinant d'une matrice a coefficients entiers par reduction modulo plusieurs nombres premiers et application du theoreme des restes chinois est completement dans le sujet.

Et c'est vrai plus generallement de presque tous les calculs d'objets a coefficients entiers (ou rationnels), mais c'est souvent plus complique a mettre en oeuvre que le calcul du determinant (surtout au niveau agreg interne), par exemple le PGCD de polynomes a coefficients rationnels. Le theoreme des restes chinois en association avec du calcul dans des corps finis premiers est incontournable en calcul formel, c'est probablement l'outil le plus utilise. Ce serait quand meme tres dommage de passer a cote dans une lecon ayant l'intitule de la 305.

parisse a écrit:

pas du tout d'accord avec vous, l'exemple que je donnais, un exercice sur le calcul du déterminant d'une matrice a coefficients entiers par réduction modulo plusieurs nombres premiers et application du théorème des restes chinois est complètement dans le sujet.

Ton exemple est bon mais je soulignais la difficulté de trouver des exercices où les nombres premiers ne sont pas juste un cache-misère.
Par exemple un exercice où on démontre qu’une équation diophantienne n’a pas de solution en réduisant modulo un truc… pourquoi modulo un premier (disons 7) alors que modulo 4, ça marche aussi ?

On a peut-être plus de structure (du moins une structure plus facile à utiliser) mais si le jury te tue ton exo avec un modulo 4, tu n’as pas l’air idiot. :-D
De toute façon, il faudra bien justifier l’intérêt de l’usage de nombres premiers dans un tel exercice parce que l’argument « ben ça marche » risque d’être reçu froidement ou par une question où justement il attend les hypothèses précises du théorème des restes chinois. Je pense qu’il est facile de coincer un candidat.

Un autre exemple de chiffrement:

https://fr.wikipedia.org/wiki/Chiffre_de_Hill

Mais là aussi il n'y a pas besoin de convoquer absolument un nombre premier même si cela facilite sans doute les choses.

On considère une matrice carrée d'ordre $r$ inversible* dans $\mathbb{Z}/n\mathbb{Z}$ avec $n\geq 26$

L'alphabet ordinaire $A,B,C,........,Z$ est converti en $0,1,2,....,25$ et on peut rajouter des symboles si $n>26$

On saucissonne un message en tranches de $r$ symboles et on applique la matrice de chiffrement à ces tranches de vecteurs à $r$ composantes. Le résultat obtenu est le message chiffré.

*: pour qu'elle soit inversible il faut et il suffit, me semble-t-il, que le déterminant soit premier avec $n$.
Quand $n$ est premier il faut que le déterminant ne soit pas divisible par $n$. Cela rend plus facile la création d'une matrice de chiffrement me semble-t-il aussi.

[size=large]Comment chiffrer avec une courbe ? Par leur entremise...[/size]

Bon, à mon avis, ce qui compte c'est que le candidat sache argumenter pour dire que "le truc" dont il parle est dans le sujet. Que les candidats aient des avis divergents, c'est évident et ce n'est pas grave du tout.

Le rapport du jury dit qu'il faut priviligier les methodes de resolution generales aux astuces specifiques (ce que j'appelle des astuces de cow-boy), la reduction modulo un nombre non premier pour resoudre un exercice particulier rentre plutot dans la seconde categorie, alors que la reduction modulo un nombre premier rentre clairement dans la premiere.

Oui, modulo 4 c'est une astuce de cow-boy, qui marchera peut-etre pour un cas particulier mais echouera generiquement, alors que travailler modulo des nombres premiers c'est une methode generale. En plus je ne vois franchement pas en quoi c'est plus difficile de calculer a la main modulo 3, 5, 7 ou 11 que modulo 4, et au moins il n'y a pas de piege, du genre 2 non nul mais pas inversible.
En calcul sur machine, on utilise en general des nombres premiers d'un peu moins de 32 bits pour pouvoir faire efficacement toutes les operations arithmetiques. On est parfois oblige de travailler sur des structures qui ne sont pas des corps, mais si on peut l'eviter on l'evite!

Un autre exemple ou utiliser un nombre premier est essentiel: tester si un polynome donne n'a pas de racine multiple (par exemple pour en chercher des racines approchees par la methode de Newton). On tire au hasard un polynome unitaire de degre disons 4, on calcule le pgcd de p et p' modulo deux ou trois nombres premiers par Euclide, des qu'on trouve un polynome constant on a gagne. Le meme calcul sur les rationnels est bien plus fastidieux.

Bon je reviens, avec le même rôle que tout à l’heure.
Nicolas met en garde à un exemple mal choisi.

Je tente un exemple métaphorique :
Utiliser le théorème des fonctions implicites pour démontrer que l’identité dans $R$ est bijective sur un intervalle peut être une source de pépins...

Mais ce n’est qu’une mise en garde, enfin, c’est ce que je comprends.

Parmi les exercices proposés par ce bouquin il y a:

1) Une "réciproque"* du petit théorème de Fermat. Résultat du à Lucas sauf erreur (je ne crois pas que ce bouquin source ce résultat)

2)Il y a aussi la divergence de la série des inverses des nombres premiers.**

3)Un exercice sur les nombres de Fermat (sous prétexte que $641$,nombre premier, divise $F_5$ j'imagine, parce que autrement cet exercice ne me semble pas très pertinent ici: il aurait mieux valu parler des nombres de Mersenne à mon humble avis)

4)Un exercice sur le fait que le groupe multiplicatif de $\mathbb{Z}/p\mathbb{Z}$ est cyclique.

5)Un exercice sur un résultat du à Frobenius je pense, Soit $G$ un groupe d'ordre $N$ et $p$ premier divise $N$
Il y a une propriété sur le nombre de solutions de l'équation $x^p=1$ dans $G$.

6)Un exercice sur le crypto-système RSA (le bouquin ne source pas la vraie origine de ce résultat, je crois qu'il y a un renvoi à un autre bouquin comme seule source me semble-t-il)

*: ce n'est pas une réciproque à proprement parler.

**: Je me demande si cet exercice n'est pas hors sujet: peut-être qu'il vaudrait mieux remplacer par la formule d'Euler: l'expression de $\zeta(s)$, avec $s>1$ comme produit infini. J'imagine que la solution à l'exercice proposé utilise cette formule.

PS:
J'ai peut-être été injuste avec les nombres de Fermat: Ceux qui sont premiers ont une forme bien particulière $2^{2^n}+1$.

On peut aussi présenter des cas particuliers du théorème de la progression arithmétique de Dirichlet.
Je ne sais plus dans quel concours il y avait une version affaiblie de ce résultat qui servait de base à un problème (ou le problème tournait autour de ce thème je ne sais plus)

Le critère d'Eisenstein en exercice me parait pas mal non?

Merci !