Des nombres palindromes

par **raog** » 21 Déc 2008, 15:08

Démontre: Chaque entier naturel qui n'est pas divisible par 10 a une multiple qui est un nombre palindrome!

Malheureusement, j'ai aucune idée, comment on pourrait le démontrer. Est-ce que quelqu'un peut m'aider?

Merci beaucoup en avance!

par **ThSQ** » 21 Déc 2008, 16:44

Salut, on peut montrer que tout nombre premier avec 10 a un multiple qui ne comporte que des 1 (le stade ultime du palindrome !). Ca a été traité il y peu sur ce forum (post de Angélique m'semble).

par **nodgim** » 21 Déc 2008, 17:47

ThSQ a écrit:Salut, on peut montrer que tout nombre premier avec 10 a un multiple qui ne comporte que des 1 (le stade ultime du palindrome !). Ca a été traité il y peu sur ce forum (post de Angélique m'semble).

Combien de 1 pour un multiple de 128 ?

par **ThSQ** » 21 Déc 2008, 17:50

128 est premier avec 10 ???

par **raog** » 21 Déc 2008, 18:07

Mais le problème concerne des nombres qui ne sont pas "divisible" par 10. Cela ne veut pas dire que ces nombres sont premier avec 10!
En plus, est-ce que quelqu'un a une idée après quoi je doit chercher pour trouver le post que ThSQ cite? Je suis trop bête... :marteau:

À propos: merci pour votres réponses!

par **ThSQ** » 21 Déc 2008, 18:13

http://www.maths-forum.com/showthread.php?t=75632

par **Zweig** » 21 Déc 2008, 18:25

Salut,

raog a écrit:Démontre: Chaque entier naturel qui n'est pas divisible par 10 a une multiple qui est un nombre palindrome!!

On considère la suite suivante modulo

:

,

On dispose de

restes : 0, 1, ..., n - 1. Si 0 est présent, alors c'est fini. Sinon, d'après le principe des tiroirs, il existe deux nombres

et

,

, qui ont le même reste modulo

, c'est-à-dire :

Comme

est premier avec

par hypothèse, alors

d'après le théorème de Gauss. Le nombre

est donc le multiple de

recherché.

par **raog** » 21 Déc 2008, 18:55

Merci bien pour le lien et pour la démonstration élégante!

Zweig a écrit:Comme est premier avec par hypothèse, [...]

Mais par hypothèse c'est un nombre qui n'est pas divisible par 10. Ca ne veut pas dire que c'est premier avec 10.

par **nodgim** » 22 Déc 2008, 10:50

Zweig a écrit:Salut,

On considère la suite suivante modulo : ,

On dispose de restes : 0, 1, ..., n - 1. Si 0 est présent, alors c'est fini. Sinon, d'après le principe des tiroirs, il existe deux nombres et , , qui ont le même reste modulo , c'est-à-dire :

Comme est premier avec par hypothèse, alors d'après le théorème de Gauss. Le nombre est donc le multiple de recherché.

Et donc, 128 en exemple, ça fait quoi ?

par **raog** » 22 Déc 2008, 11:13

La démonstration de Zweig inclut seulement les nombres premier avec 10. Bien sûr, tous les nombres qui sont divisible par deux n'ont pas un multiple qui ne comporte que des "1", car aucun multiple d'un nombre divisible par deux est impair!
Alors, la démonstration est un premier pas, mais il faut le montre pour les entiers divisible par 2 et les entiers divisible par 5 maintenant.

Évidemment:
128 * 33 = 4224
128 * 66 = 8448
128 * 318 = 40704
128 * 333 = 42624
128 * 348 = 44544
128 * 363 = 46464
128 * 378 = 48384
128 * 3168 = 405504
128 * 3333 = 426624
128 * 3498 = 447744
128 * 3663 = 468864
128 * 3828 = 489984

et autre exemple:
125 * 417 = 52125
125 * 421 = 52625
125 * 459 = 57375
125 * 463 = 57875

par **nodgim** » 22 Déc 2008, 11:21

raog a écrit:La démonstration de Zweig inclut seulement les nombres premier avec 10. Bien sûr, tous les nombres qui sont divisible par deux n'ont pas un multiple qui ne comporte que des "1", car aucun multiple d'un nombre divisible par deux est impair!
Alors, la démonstration est un premier pas, mais il faut le montre pour les entiers divisible par 2 et les entiers divisible par 5 maintenant.

Évidemment:
128 * 33 = 4224
128 * 66 = 8448
128 * 318 = 40704
128 * 333 = 42624
128 * 348 = 44544
128 * 363 = 46464
128 * 378 = 48384
128 * 3168 = 405504
128 * 3333 = 426624
128 * 3498 = 447744
128 * 3663 = 468864
128 * 3828 = 489984

et autre exemple:
125 * 417 = 52125
125 * 421 = 52625
125 * 459 = 57375
125 * 463 = 57875

Ben oui, y a plus qu'à.. :ptdr:

par **raog** » 22 Déc 2008, 11:35

:ptdr: Je seulement voulais montrer qu'il y a des raisons de croire que, vraiment, tous les entiers divisible par 2 ou 5 ont des multiple palindrome.
Naturellement cela n'est pas une démonstration et malheureusement je n'ai pas du tout une démonstration.

par **cyrix** » 22 Déc 2008, 19:30

"Insbesondere sind Diskussionen von Lösungswegen
im Internet nicht zulässig" - Teilnahmebedingungen Bundeswettbewerb Mathematik 2009

par **Doraki** » 23 Déc 2008, 02:10

On prend un nombre n ni divisible par 10 ni premier avec 10.
n s'écrit m*p avec m premier avec 10, et p = 2^k ou 5^k.

On commence d'abord par trouver 2 entiers a et b tels que a*m = 10^b-1,
et on se ramène à étudier le cas de a*n = (a*m)*p = (10^b-1)*p.
Et quitte à devoir augmenter a et b, on peut supposer b > 2k.

Ensuite, on note que 10^k est un multiple de p, et donc (10^k-p)+10^k*("p mod 10^k en renversant les chiffres") aussi, donc il s'écrit p*q.
Et alors q*(p*(10^b-1)) est un palindrome.

Par exemple, en ayant b=13 et p = 2^4 = 16, on a que
3813124 * 16 = 61009984, et donc
3813124 * (16*(10^b-1)) = 61009984 * (10^b-1) = 610099839999938990016.

par **Mathusalem** » 23 Déc 2008, 05:47

Doraki a écrit:On prend un nombre n ni divisible par 10 ni premier avec 10.
(...)

J'ai beau réfléchir (remarque sérieuse..) je ne comprends pas pourquoi on fait l'assertion "ni premier avec 10". Est-ce que le fait qu'un nombre ne soit pas divisible par 10 n'exclut pas d'office le fait qu'il soit premier avec 10 ?

Je n'ai pas pris le temps de comprendre la preuve, je ne sais pas si cette assertion est nécessaire pour poser une hypothèse, ou si la répétition a été faite par inadvertance. Merci

A+

par **Doraki** » 23 Déc 2008, 12:00

Si n est premier avec 10 on a déjà donné une preuve dans les pages d'avant.
Si n est divisible par 10 ben out multiple termine par un 0 et ça peut pas être un palindrome.

Donc ilrestait à étudier le cas d'un nombre ni divisible par 10 ni premier avec 10, comme par exemple, 2.

par **raog** » 23 Déc 2008, 12:35

Doraki a écrit:Par exemple, en ayant b=13 et p = 2^4 = 16, on a que
3813124 * 16 = 61009984, et donc
3813124 * (16*(10^b-1)) = 61009984 * (10^b-1) = 610099839999938990016.

J'ai une question: Où est-ce que se trouve n dans cet exemple? Evidemment, q = 3813124, mais comment détermines-tu q?
Est-ce que c'est correcte que 10^k - p + 10^k * ("p mod 10^k en renversant les chiffres") = q? p mod 10^k est toujours p, n'est-ce pas?
Par exemple: 2^5 mod 10^5 = 2^5, car 0*10^5 + 2^5 = 2^5

par **Doraki** » 23 Déc 2008, 12:44

euh ouais "p mod k en renversant les chiffres" c'est pas très bien dit.
Je veux dire qu'il faut prendre p en complétant à gauche avec autant de 0 qu'il faut pour avoir k chiffres, et puis renverser les chiffres.
Dans l'exemple, p c'est 16.
k=4 donc il me faut 4 chiffres : 0016
Je retourne : 6100
Maintenant, (10^k-p)+10^k*6100 ça fait 61009984, et c'est un multiple de 16 :
10^k = 5^k*2^k = 5^k*p, donc
(10^k-p)+10^k*6100 = p*(5^k-1+5^k*6100) = p*3813124.

Et dans l'exemple, n c'est n'importe quel diviseur de 16*(10^b-1).

par **raog** » 23 Déc 2008, 13:49

Tout cela est vraiment intéressant, mais il nous faut une justification.
En premier, nous avons montré qu'il y a 2 entiers a et b tels que a*m = 10^b - 1. C'est clair, parce qu'il y a un multiple de m qui ne comporte que des 1. Et donc il y a aussi un multiple qui ne comporte que des 9.
Mais pourquoi peut-on dire qu'il est possible de augmenter a et b tels que b > 2k? Nous ne savons pas s'il y a plusieurs entiers a et b tels que a*m = 10^b - 1!

q*(p*(10^b-1)) est un palindrome. Ben, mais c'est plutôt comme un miracle. Je ne peut pas trouver une raison!

En tout cas, merci beaucoup pour la réponse! C'est déjà très utile :)

par **Doraki** » 23 Déc 2008, 14:09

Pour pouvoir augmenter b, suffit de voir que
(10^b-1) * (10^b+1) = 10^(2b)-1 : avec ça tu passes de b à 2b.

Et que q*n est un palindrome, ben q a été choisi vraiment exprès pour faire apparaître les bons chiffres aux bons endroits... mais c'est pas marrant à vouloir vraiment démontrer (c'est ça l'ennui avec les problèmes sur les palindromes)

Des nombres palindromes

Des nombres palindromes

Qui est en ligne