Salut nodgim,

pour p=2, 3, 5, 7, il est clair qu'il n'existe aucun nombre n réfractaire à p : par exemple pour p=7, si on change le dernier chiffre de n par 0, puis 1, 2, 3, 4, 5, 6, un des 7 nombres obtenus est divisible par 7.

Si p>100, alors 11 est réfractaire à p, car les premiers multiples de p sont 0 qu'on ne peut obtenir en changeant un seul chiffre de 11, puis p qu'on ne peut non plus obtenir car 11 n'a pas assez de chiffres.

Si p est à deux chiffres et différent de 11, on écrit la liste des multiples de p compris entre 00 et 99, et on trouve un nombre réfractaire à p en prenant un chiffre des unités et un chiffre des dizaines qui ne sont pas dans la liste.

Par exemple, si p=17, la liste est 00;17;34;51;68;85, la liste des chiffres des unités est donc 0;1;4;5;7;8 et celle des chiffres des dizaines est 0;1;3;5;6;8, n=22 ou n=43 sont donc deux nombres réfractaires à p (il y en a d'autres).

Le pire cas, p=13, fournit la liste 00;13;26;39;52;65;78;91, et donc 44 est réfractaire à 13.

Il reste le cas de p=11 qui ne peut se régler ainsi. Mais j'ai trouvé n=545 qui est réfractaire à 11, en utilisant le critère de divisibilité par 11. Si on change le premier chiffre, on obtient 045;145;...;945. La somme des chiffres de rang impair est 5;6;...;14, et celle des chiffres de rang pair est 4 : la différence entre ces deux sommes ne sera jamais un multiple de 11. De même avec le deuxième ou le troisième chiffre.

Ah je vois, mon énoncé n'était pas assez précis....

Je corrige l'énoncé en précisant que n > p. 

Sinon, c'est trop facile.

Ça ne me parait pas beaucoup plus dur, une fois qu'on a l'idée d'utiliser le principe des tiroirs.

Si le nombre premier p a k chiffres, il y a au plus 9 multiples de p (en commençant par 0) qui ont k chiffres (sans compter 0 qui est aussi multiple de p). Il y a 9k façons de changer exactement un des chiffres d'un de ces multiples. Donc cela fait au plus 10*(9k+1) nombres à k chiffres qui ne sont pas réfractaires à p.

Pour un nombre premier à 3 chiffres (k=3), cela fait au plus 280 nombres à 3 chiffres qui ne sont pas réfractaires à p. Donc si p<=718, par le principe des tiroirs, il existe un nombre réfractaire à p à trois chiffres parmi les nombres de [p+1;999] (ensemble de cardinal >=281).

Mais si k=3 et p>718, on regarde les multiples de p à <=4 chiffres (il y en a au plus 14), il y a donc au plus 14*(9*4+1)=518 nombres à 4 chiffres réfractaires à p, donc là encore le principe des tiroirs assure qu'il existe un nombre à 4 chiffres réfractaire à p.

Si k>3, la même méthode fonctionne, et même encore mieux car 10*(9k+1) augmente moins vite que le nombre de nombres à k chiffres.

Reste les cas k=1 et k=2. Si p n'a qu'un chiffre, il n'existe aucun nombre réfractaire à p (cf mon message précédent). Si p a deux chiffres, il existe à chaque fois un nombre réfractaire à p. Le cas le plus dur est 11, pour lequel n=545 convient. Pour les autres, il suffit de traiter les nombres premiers un par un, c'est beaucoup plus facile à trouver que pour 11.

@ Bastidol :

Si tu choisis n = p + 1 , ça ne marche que si p se termine par 9. Car si p se termine par 3, 7 ou 1, alors ton chiffre des unités sera 4, 8 ou 2 qu'il suffira de ramener à 3, 7 ou 1 pour retrouver p.

Oui c'est ça Bastidol.

Dans le message précédent, tu avais écrit qu'il fallait démontrer que p+1 était réfractaire, d'où ma mise en garde.