Divisibilité / Expression générale / Recherche / Seconde

[Khwartz]

Bonjour,

Je cherche à exprimer les critères de divisibilité de manière la plus générale possible, d'abord en base 10 puis pour n'importe-quelle base.

Je suis parti de l'idée de développer l'expression du nombre entier E dont on veut vérifier la divisibilité par le nombre entier M dans la base 10, en remplaçant à chaque fois 10 par la somme (M+N) de façon à pouvoir balancer M du côté de MP et ainsi factoriser, simplifier, etc., soit :



mais après toute une journée passée dessus je cale car je ne fais que soit tourner en rond, soit d'aboutir dans des impasses.

Il me semble aussi que cela doit à voir avec l’arithmétique modulaire mais je n'arrive pas à l'utiliser ici. Si quelqu'un peu me donner des pistes ? Ou me proposer une autre stratégie ?

Remarque : je suis moins intéressé par les démonstrations elles-mêmes, que par le raisonnement stratégique et euristique qui va conduire à la dite démonstration ...
-----

[invite4492c379]

Bonjour,

Je cherche à exprimer les critères de divisibilité de manière la plus générale possible, d'abord en base 10 puis pour n'importe-quelle base.

Je suis parti de l'idée de développer l'expression du nombre entier E dont on veut vérifier la divisibilité par le nombre entier M dans la base 10, en remplaçant à chaque fois 10 par la somme (M+N) de façon à pouvoir balancer M du côté de MP et ainsi factoriser, simplifier, etc., soit :



mais après toute une journée passée dessus je cale car je ne fais que soit tourner en rond, soit d'aboutir dans des impasses.

Il me semble aussi que cela doit à voir avec l’arithmétique modulaire mais je n'arrive pas à l'utiliser ici. Si quelqu'un peu me donner des pistes ? Ou me proposer une autre stratégie ?

Remarque : je suis moins intéressé par les démonstrations elles-mêmes, que par le raisonnement stratégique et euristique qui va conduire à la dite démonstration ...

Hello,

fais simplement une division ... tu trouveras des résultats intéressants comme tout nombre dont la somme des chiffres de rang impair égale au modulo près la somme des chiffres de rang pair est divisible par 11, quelle que soit la base entière b>1.

[Khwartz]

ok, merci du conseil mais qu'est-ce qui te fait dire qu'il faut faire une division pour aller dans la bonne direction ? et la division de quoi par quoi, de mon expression avec (M+N) par la M de MP ?

[invite4492c379]

ok, merci du conseil mais qu'est-ce qui te fait dire qu'il faut faire une division pour aller dans la bonne direction ? et la division de quoi par quoi, de mon expression avec (M+N) par la M de MP ?

Non tu poses une division comme si tu divisais à la main pour obtenir une relation du genre. Après tu remarqueras vite qu'il te suffit de connaître b^n modulo d, où b est la base, n un entier>0 et d le nombre dont tu cherches un test de divisibilité.

[A voir en vidéo sur Futura]

[Khwartz]

Désolé, mais quand tu dis de poser une division, je ne sais pas quel sont le diviseur et le dividende dont tu parles. Peux-tu me préciser STP?

[invite4492c379]

Pour comprendre comment ça marche tu prends le dividende A égale à a_nbⁿ+...a₁.b+a₀, le diviseur égale au nombre d dont tu veux déterminer le critère de divisibilité et tu calcules le quotient et le reste.
par exemple si on prend en base b>1, d=11 :
on a
1=0.11+1
10=1.11-1
100=(b-1)11+1
1000=((b-1)b-1)11-1

d'où A=a_nbⁿ+...a₁.b+a₀=a₀-a₁+...+(-1)ⁿa_n + 11.k
donc 11 divise A si la différence entre la somme des chiffres de rang impair et la somme des chiffres de rang pair est elle-même un multiple de 11 (revient à dire congru à 0 modulo 11)

Ici ça s'arrange bien car b+1=11 dans toute base entière b>1.

[Khwartz]

Très bien, merci beaucoup pour cet éclaircissement

Puisque c'est la stratégie de recherche de réponses qui m'intéresse le plus, qu'est-ce qui t'a conduit à écrire :

1=0.11+1
10=1.11-1
100=(b-1)11+1
1000=((b-1)b-1)11-1

et non pas :

1=0.11+1
10=0.11+10
100=(b-1)11+1
1000=8.121+2.11+10 ?

[invite4492c379]

Très bien, merci beaucoup pour cet éclaircissement

Puisque c'est la stratégie de recherche de réponses qui m'intéresse le plus, qu'est-ce qui t'a conduit à écrire :

1=0.11+1
10=1.11-1
100=(b-1)11+1
1000=((b-1)b-1)11-1

et non pas :

1=0.11+1
10=0.11+10
100=(b-1)11+1
1000=8.121+2.11+10 ?

Les deux sont équivalentes, je trouve la première plus simple. Si tu essayes de trouver un test de divisibilité par 7 en base 10 par exemple tu peux en trouver plusieurs, certains seront plus adaptés que d'autres dans certaines situations.

[Khwartz]

ok, mais alors pourquoi tu n'as pas écris plutôt :

1=0.b+1
10=1.b-1
100=(b-1)b+1
1000=((b-1)b-1)b-1 ?

[invite4492c379]

(...)

1000=8.121+2.11+10 ?

Oooops ... lu un peu trop rapidement, je me mets en une base b>1 ... la dernière ligne n'est pas une écriture valide dans tous les cas.

[invite4492c379]

Parceque j'ai écrit les deux et je ne garde que celle qui me semble la plus apropriée
Il n'y a pas de formule magique qui te donne la meilleure. Essaye de trouver plusieurs critères de divisibilité par 7 en base 10 ... tu comprendras.

[Khwartz]

Désolé, j'ai buggé et ai pas pu corriger mon précédent post. Voici donc mon post corrigé :

----------------------

1=0.11+1
10=1.11-1
100=(b-1)11+1
1000=((b-1)b-1)11-1

Je ne comprends pas : tu écris les expressions comme si 11 était en fait la base, car en effet, en base 11 on écrirait comme je l'avais fait :

1=0.11+1
10=0.11+10
100=9.11+1
1000=8.121+2.11+10

mais tu utilises quand même "b", que tu avais définis comme la base, non pas en tant que base mais en tant que coefficient complémentaire, même pas à 11 mais à 10 ; comme expliques-tu la logique de ta démarche STP ?

[Khwartz]

Oooops ... lu un peu trop rapidement, je me mets en une base b>1 ... la dernière ligne n'est pas une écriture valide dans tous les cas.

Elle est bien valide en base 11, n'est-ce pas ? J'aurais pu écrire : 1000=8.11^2+2.11^1+10.10^0 pour être plus explicite

[invite4492c379]

Désolé, j'ai buggé et ai pas pu corriger mon précédent post. Voici donc mon post corrigé :

----------------------

1=0.11+1
10=1.11-1
100=(b-1)11+1
1000=((b-1)b-1)11-1

Je ne comprends pas : tu écris les expressions comme si 11 était en fait la base, car en effet, en base 11 on écrirait comme je l'avais fait :

1=0.11+1
10=0.11+10
100=9.11+1
1000=8.121+2.11+10

mais tu utilises quand même "b", que tu avais définis comme la base, non pas en tant que base mais en tant que coefficient complémentaire, même pas à 11 mais à 10 ; comme expliques-tu la logique de ta démarche STP ?

Quelle que soit la base b>1, b+1 s'écrit toujours 11_b .
3 en base 2 s'écrit 11₂
11 en base 10 s'écrit 11₁₀
17 en base 16 s'écrit 11₁₆
etc ...

11_b=1.b¹+1.b⁰ = b+1

[Khwartz]

Parceque j'ai écrit les deux et je ne garde que celle qui me semble la plus apropriée

Comme je te l'ai dit : c'est moins la réponse qui m'intéresse, et même je ne la veux même pas, que la démarche ou des pistes, tant que j'en ai besoin pour me débloquer. donc si tu me "cache" une partie de ta démarche, ça ne m'arrange pas du tout :/

Il n'y a pas de formule magique qui te donne la meilleure. Essaye de trouver plusieurs critères de divisibilité par 7 en base 10 ... tu comprendras.

J'ai déjà démontré les critères pour 4, 5, 6 et 9 si je me souviens bien, mais pour 7, j'ai séché hier et j'ai donc décidé d'être plus ambitieux pour trouver une logique plus générale de "prospection" de principe d'expression des critères de divisibilité. je vais donc au final l'appliquer ce que je trouverai avec toi peut-être à la (re)découverte des critères de divisibilité par 7, mais j'ai vraiment besoin de comprendre la logique, la stratégie exactement, je ne suis guère intéressé par les "intuitions" ou les "inspirations inexplicables" Ce que je souhaite c'est du "reproductible", du "recyclable" pour des cas proches ou plus éloignés

[Khwartz]

Quelle que soit la base b>1, b+1 s'écrit toujours 11_b .
3 en base 2 s'écrit 11₂
11 en base 10 s'écrit 11₁₀
17 en base 16 s'écrit 11₁₆
etc ...

11_b=1.b¹+1.b⁰ = b+1

je suis bien d'accord, mais bien que tu avais écris "par exemple si on prend en base b>1, d=11 :" je prenais tes "11" pour une écriture en base 10 car je n'avais pas réalisé que ta donnée de la base b>1 s'appliquait déjà à d=11 (d'où l'intérêt de l'écriture avec indices que tu viens d'utiliser qui m'ôte effectivement toute ambiguïté ) - je crois que je vais allé coucher mes os pour reprendre le travail un autre fois

[invite4492c379]

Comme je te l'ai dit : c'est moins la réponse qui m'intéresse, et même je ne la veux même pas, que la démarche ou des pistes, tant que j'en ai besoin pour me débloquer. donc si tu me "cache" une partie de ta démarche, ça ne m'arrange pas du tout :/

Je ne cache rien ... de plusieurs relations tu gardes celle qui te semble la plus simple.

J'ai déjà démontré les critères pour 4, 5, 6 et 9 si je me souviens bien, mais pour 7, j'ai séché hier et j'ai donc décidé d'être plus ambitieux pour trouver une logique plus générale de "prospection" de principe d'expression des critères de divisibilité. je vais donc au final l'appliquer ce que je trouverai avec toi peut-être à la (re)découverte des critères de divisibilité par 7, mais j'ai vraiment besoin de comprendre la logique, la stratégie exactement, je ne suis guère intéressé par les "intuitions" ou les "inspirations inexplicables" Ce que je souhaite c'est du "reproductible", du "recyclable" pour des cas proches ou plus éloignés

Le reproductible ?
En base 10 pour un critère de divisibilité par d :
Tu calcules les restes de la division de 10ⁿ par d en commençant à n=0, en incrémentant n de 1 jusqu'à former un cycle. Exemple avec 7, tu vas trouver 1,3,2,6,4,5.
Tu veux tester avec un nombre A=a_n..a₁a₀, tu calcules A'=a₀*1+a₁*2+a₂*3+a₃*6+a₄*4+a₅*5+a₆*1+...
7 divise A ssi 7 divise A', si A' est trop grand tu recommences ...
Dans le cycle 1,3,2,6,4,5 tu peux remplacer n'importe lequel des chiffres par le chiffre moins 7. Cela signifie que si tu utilises 1,3,2,6,4,5 ou 1,3,2,-1,-3,-5 c'est pareil. Tu remarques que tu as en fait 2 fois 3 chiffres au signe près ... des regroupements semblent possibles.

[invite7863222222222]

Photon je sais pas pour les autres mais je comprends pas grand chose.

C'est sans doute juste mais les relations sont données trop vite sans explications et on comprends pas bien la démarche. Je pense que ça pourra éviter des casses têtes de donner juste un peu plus de précisions.

[invite4492c379]

Photon je sais pas pour les autres mais je comprends pas grand chose.

C'est sans doute juste mais les relations sont données trop vite sans explications et on comprends pas bien la démarche. Je pense que ça pourra éviter des casses têtes de donner juste un peu plus de précisions.

Ok ... je vais essayer d'être un peu plus rigoureux ...
Soit b un entier >1,
on a : bⁿ = (-1)ⁿ [b+1]

Si on exprime cette relation en base b :

10_bⁿ=(-1)ⁿ [11_b]

a_n...a₁a_{0b =} a_0b+a_2b+... - (a_1b+a_3b+...) [b+1]

avec a_n...a₁a_0b l'écriture en base b du nombre

[Khwartz]

Je ne cache rien ... de plusieurs relations tu gardes celle qui te semble la plus simple.

Ben si, justement, tu ne m'avais pas dit au départ que tu avais cherché plusieurs relations et que celles que tu me présentaient était les plus simples.

Le reproductible ?
En base 10 pour un critère de divisibilité par d :
Tu calcules les restes de la division de 10ⁿ par d en commençant à n=0, en incrémentant n de 1 jusqu'à former un cycle. Exemple avec 7, tu vas trouver 1,3,2,6,4,5.
Tu veux tester avec un nombre A=a_n..a₁a₀, tu calcules A'=a₀*1+a₁*2+a₂*3+a₃*6+a₄*4+a₅*5+a₆*1+...
7 divise A ssi 7 divise A', si A' est trop grand tu recommences ...

Oui, extra! Merci pour la méthode

Dans le cycle 1,3,2,6,4,5 tu peux remplacer n'importe lequel des chiffres par le chiffre moins 7. Cela signifie que si tu utilises 1,3,2,6,4,5 ou 1,3,2,-1,-3,-5 c'est pareil. Tu remarques que tu as en fait 2 fois 3 chiffres au signe près ... des regroupements semblent possibles.

ok, je vais creuser ça. Merci pour ton aide Photon

[invite4492c379]

Ben si, justement, tu ne m'avais pas dit au départ que tu avais cherché plusieurs relations et que celles que tu me présentaient était les plus simples.

(...)

Oui tu trouves deux relations, celle que tu as citées

[Khwartz]

Ok ... je vais essayer d'être un peu plus rigoureux ...
Soit b un entier >1,
on a : bⁿ = (-1)ⁿ [b+1]

Merci Photon pour cette nouvelle expression très générale

Pour ce qui me concerne, ce qui me manque à chaque fois, et c'est bien normal parce que presque personne ne prends le temps de le faire, c'est d'expliquer comment tu as eu cette idée de poser cette expression-là.

C'est comme la démarche que j'avais adoptée dans ma recherche, quelle puisse aboutir ou non à quelque chose d'intéressant, je sais pourquoi je l'avais choisie et je te l'ai écrit : pour que le diviseur apparaisse un maximum de fois dans l'expression afin de pouvoir ensuite effectuer des simplifications et supprimer des termes.

Si c'est juste qu'un prof te l'as montrée, c'est cool avec moi, mais c'est juste que je voudrais savoir TOUTE la démarche intellectuelle qui conduit à "pondre" telle expression, à faire telle recherche plutôt qu'une autre, et ce, autant que possible en pas à pas pour que se soit bien clair et donc facilement analysable en tant que démarche

Si on exprime cette relation en base b :

10_bⁿ=(-1)ⁿ [11_b]

Désolé mais soit la b=3 et n=2, n'a-t-on pas :

10_bⁿ=3₁₀²=9, alors que :

(-1)² [4₁₀]=4 ?

[invite7863222222222]

Ok ... je vais essayer d'être un peu plus rigoureux ...
Soit b un entier >1,
on a : bⁿ = (-1)ⁿ [b+1]

Si on exprime cette relation en base b :

10_bⁿ=(-1)ⁿ [11_b]

a_n...a₁a_{0b =} a_0b+a_2b+... - (a_1b+a_3b+...) [b+1]

avec a_n...a₁a_0b l'écriture en base b du nombre

Je ne comprends pas la dernière relation par exemple.


Que signifie les crochets ?

De même que vaut a_0b ?

Un exemple concret serait peut être plus parlant.

[invite7863222222222]

on a : bⁿ = (-1)ⁿ [b+1]

Si on prends b=4, n=3 on a 4³ = 64 pourquoi ça serait égal à (-1)[5+1] (-6 ?) ?

[invite4492c379]

Tu sais à ce niveau là il n'y a pas vraiment d'origine à ma «démarche». Ça se confond entre répondre à des énigmes, cours d'arithmétiques, entrainement à des chiffres et des lettres, écriture d'algos, lecture ... je te l'ai dit : il n'y a pas de méthode magique.
La méthodes des puissances de la base modulo le diviseur est générale, mais par exemple pour la base 10 et d=7 tu as aussi 7|an..a0 ssi 7|(an..a1-2*a0) ...

Sinon en base 3 :
10²=100=11*2+1=1[11]

[Khwartz]

"a0b" veut dire : coefficient indice zéro de l'expression du nombre entier dans la base "b"

[Khwartz]

Tu sais à ce niveau là il n'y a pas vraiment d'origine à ma «démarche». Ça se confond entre répondre à des énigmes, cours d'arithmétiques, entrainement à des chiffres et des lettres, écriture d'algos, lecture ...

Ok, pas de souci, merci de m'avoir précisé

je te l'ai dit : il n'y a pas de méthode magique.

je n'ai jamais demandé de "méthode magique" mais "logique" lol, quelqu'un serait-il dyslexique ?
Perso, je n'ai que ça, et plus j'en ai, mieux ça me paraît, en tout cas ça m'a souvent servi ; d'autant que pour trouver des méthodes générales et systématiques de résolution, ça demande de vraiment comprendre se qui se passe. Mais une fois trouvée, là du coup, oui, ça devient tellement fastoche que ça en devient presque magique. Et mon test en fait c'est de me demander si la méthode pourrait être programmée dans un ordi (un de mes grands projets : formaliser complètement le raisonnement humain ).

La méthodes des puissances de la base modulo le diviseur est générale,

C'est donc ce qu'il me faut

mais par exemple pour la base 10 et d=7 tu as aussi 7|an..a0 ssi 7|(an..a1-2*a0) ...

Sinon en base 3 :
10²=100=11*2+1=1[11]

Merci pour ces dernières pistes, je vais les creuser certainement un peu plus tard, car après quelque quarante heures de veille, je commence à saturer

Bien cordialement, en te remerciant encore de ton aide.

[invite4492c379]

Je ne comprends pas la dernière relation par exemple.


Que signifie les crochets ?

De même que vaut a_0b ?

Un exemple concret serait peut être plus parlant.

j' utilise les crochets pour noter le modulo, quant à a_n..a_0b, cela représente l'écriture d'un nombre en base b (d'où indice b), les a₀ à a_n étant les chiffres de ce nombre (a₀ le chiffre le plus à droite et a_n le chiffre le plus à gauche). D'une manière générale, on a pour tout chiffre a_i 0<a_i<b.

[invite4492c379]

Si on prends b=4, n=3 on a 4³ = 64 pourquoi ça serait égal à (-1)[5+1] (-6 ?) ?

Dans la suite je souligne les écritures en base 4 et ne souligne pas les écritures en base 10 (avec = pour la congruence)

4³ = 64 = 65-1 = 5*13 -1 = -1 [5]
en base 4 :
10³ = 1000 = 1001-1 = 11*31-1 = -1 [11]

[Khwartz]

Super bien clarifié