{"id":643,"date":"2025-02-04T14:17:21","date_gmt":"2025-02-04T13:17:21","guid":{"rendered":"https:\/\/lig-membres.imag.fr\/denisb\/?p=643"},"modified":"2025-02-04T14:17:47","modified_gmt":"2025-02-04T13:17:47","slug":"critere-binaire-de-divisibilite","status":"publish","type":"post","link":"https:\/\/lig-membres.imag.fr\/denisb\/critere-binaire-de-divisibilite\/","title":{"rendered":"Crit\u00e8re (binaire) de divisibilit\u00e9"},"content":{"rendered":"<div>\n<div>En r\u00e9fl\u00e9chissant \u00e0 un sujet d&#8217;examen pour mes \u00e9tudiants (en architecture des ordinateurs) je suis tomb\u00e9 sur cet algorithme qui permet de d\u00e9terminer la divisibilit\u00e9 d&#8217;un nombre N par D en op\u00e9rant (presque) seulement des divisions par 2 (en fait, il faut aussi pouvoir faire des additions simples ou des soustractions, mais comme les soustractions sont souvent moins simples, dans la suite, on se limitera \u00e0 faire des additions &#8220;simples&#8221;).<\/div>\n<div><\/div>\n<div>Supposons donc que l&#8217;on veuille trouver si N (un nombre quelconque positif) est multiple de D (un nombre quelconque positif), par exemple, on veut trouver si 1789 (N) est multiple de 13 (D) \u00a0:<\/div>\n<ul>\n<li>(Cas 1 : N pair, D pair) : Si N et D sont tous les deux pairs, on peut les diviser tous les deux par 2 (ce qui est assez facile en d\u00e9cimal et imm\u00e9diat sur machine ou quand on pense binaire). Le nouveau N sera multiple du nouveau D ssi le pr\u00e9c\u00e9dent N \u00e9tait multiple du pr\u00e9c\u00e9dent D. Le probl\u00e8me est donc r\u00e9duit \u00e0 un probl\u00e8me plus petit. On peut r\u00e9p\u00e9ter cette op\u00e9ration jusqu&#8217;\u00e0 ce que N ou D soient impairs.<\/li>\n<\/ul>\n<div>Supposons donc maintenant que N ou D, ou les deux sont impairs.<\/div>\n<ul>\n<li>(Cas 2 : N impair, D pair) : Si N est impair et D pair, alors N ne sera pas multiple de D. En effet, si N \u00e9tait multiple de D, comme D est pair, N serait pair, ce qu&#8217;il n&#8217;est pas. Donc N n&#8217;est pas multiple de D. Le probl\u00e8me est clos.<\/li>\n<li>(Cas 3 : N pair, D impair) : Si N est pair et D impair, alors on peut diviser N par 2. Comme D est impair, ce n&#8217;est pas la parit\u00e9 de N qui permet N d&#8217;\u00eatre multiple de D. On peut donc r\u00e9p\u00e9ter cette op\u00e9ration jusqu&#8217;\u00e0 ce que N soit impair.<\/li>\n<\/ul>\n<div>On arrive donc \u00e0 la situation o\u00f9 l&#8217;on cherche si un nombre impair N est multiple d&#8217;un nombre impair D.<\/div>\n<ul>\n<li>(Cas 4 : N impair, D impair) : On peut additionner D de N (ou le soustraire), cela ne change pas le crit\u00e8re de divisibilit\u00e9 de N par D. Le nouveau N est pair (par addition de deux nombres impairs), ce qui nous ram\u00e8ne au cas pr\u00e9c\u00e9dent (cas 3).<\/li>\n<\/ul>\n<div>Comment cela se termine ?<\/div>\n<ul>\n<li>cela se termine par la n\u00e9gative dans le cas 2 : N n&#8217;est pas multiple de D.<\/li>\n<li>cela peut aussi se terminer si on arrive \u00e0 un moment \u00e0 N=0 ou N=D. Dans ce cas, N est (trivialement) multiple de D.<\/li>\n<li>cela peut aussi se terminer si on arrive \u00e0 un moment avec N entre 1 et D-1. Dans ce cas, N n&#8217;est pas multiple de D.<\/li>\n<\/ul>\n<div>\u00a0Dans tous les cas cela se termine parce que l&#8217;un des deux nombres est r\u00e9duit dans les \u00e9tapes 1, 2 et 3, et que dans le cas 4, il N n&#8217;est pas r\u00e9duit imm\u00e9diatement, puisqu&#8217;il y a une addition N+D rempla\u00e7ant N, mais \u00e0 l&#8217;\u00e9tape suivante, on a le cas 3 qui r\u00e9duit N en le divisant par 2. (cas 4 suivi de 3 : N &lt;= (N+D)\/2, cela r\u00e9duit N si N&gt;D, car si N&gt;D, N+N&gt;N+D, donc (N&gt;(N+D)\/2, le nouveau N sera plus petit que le pr\u00e9c\u00e9dent)<\/div>\n<div><\/div>\n<div>Exemple pour 1789 et 13 :<\/div>\n<ul>\n<li>cas 4 (1789 impair\/ 13 impair) : 1789+13=1802 (pair), on se retrouve dans le cas 3<\/li>\n<li>cas 3 (1802 pair\/ 13 impair) : 1802 divis\u00e9 par 2 \u00e9gal 901 (impair), on se retrouve dans le cas 4<\/li>\n<li>cas 4 (901 impair\/ 13 impair) : 901+13=914 (pair), on se retrouve dans le cas 3<\/li>\n<li>cas 3 (914 pair\/ 13 impair) : 914 divis\u00e9 par 2 \u00e9gal 457 (impair), on se retrouve dans le cas 4<\/li>\n<li>cas 4 (457 impair\/ 13 impair) : 457+13=470 (pair), on se retrouve dans le cas 3<\/li>\n<li>cas 3 (470 pair\/ 13 impair) : 470 divis\u00e9 par 2 \u00e9gal 235 (impair), on se retrouve dans le cas 4<\/li>\n<li>cas 4 (235 impair\/ 13 impair) : 235+13=248 (pair), on se retrouve dans le cas 3<\/li>\n<li>cas 3 (248 pair\/ 13 impair) : 248 divis\u00e9 par 2 \u00e9gal 124 (pair), on se retrouve dans le cas 3<\/li>\n<li>cas 3 (124 pair\/ 13 impair) : 124 divis\u00e9 par 2 \u00e9gal 62 (pair), on se retrouve dans le cas 3<\/li>\n<li>cas 3 (62 pair\/ 13 impair) : 62 divis\u00e9 par 2 \u00e9gal 31 (impair), on se retrouve dans le cas 4<\/li>\n<li>cas 4 (31 impair\/ 13 impair) : 31+13=44 (pair), on se retrouve dans le cas 3<\/li>\n<li>cas 3 (44 pair\/ 13 impair) : 44 divis\u00e9 par 2 \u00e9gal 22 (pair), on se retrouve dans le cas 3<\/li>\n<li>cas 3 (22 pair\/ 13 impair) : 22 divis\u00e9 par 2 \u00e9gal 11 (impair)<\/li>\n<\/ul>\n<div>\u00a0On est arriv\u00e9 \u00e0 la fin, 11 est plus petit que 13, il est clair qu&#8217;il n&#8217;est pas divisible par 13.<\/div>\n<div>\u00a0Donc 1789 n&#8217;est pas divisible par 13.<\/div>\n<div><\/div>\n<\/div>\n<div>Pour en savoir plus : <a href=\"https:\/\/github.com\/denisb\/notebooks\/blob\/master\/Misc\/Crit%C3%A8reDivisibilit%C3%A9.ipynb\">voir ici<\/a><\/div>\n","protected":false},"excerpt":{"rendered":"<p>En r\u00e9fl\u00e9chissant \u00e0 un sujet d&#8217;examen pour mes \u00e9tudiants (en architecture des ordinateurs) je suis tomb\u00e9 sur cet algorithme qui [&hellip;]<\/p>\n","protected":false},"author":42,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"site-sidebar-layout":"default","site-content-layout":"","ast-site-content-layout":"default","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","theme-transparent-header-meta":"default","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"set","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"footnotes":""},"categories":[202],"tags":[],"class_list":["post-643","post","type-post","status-publish","format-standard","hentry","category-202"],"_links":{"self":[{"href":"https:\/\/lig-membres.imag.fr\/denisb\/wp-json\/wp\/v2\/posts\/643","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/lig-membres.imag.fr\/denisb\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/lig-membres.imag.fr\/denisb\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/lig-membres.imag.fr\/denisb\/wp-json\/wp\/v2\/users\/42"}],"replies":[{"embeddable":true,"href":"https:\/\/lig-membres.imag.fr\/denisb\/wp-json\/wp\/v2\/comments?post=643"}],"version-history":[{"count":3,"href":"https:\/\/lig-membres.imag.fr\/denisb\/wp-json\/wp\/v2\/posts\/643\/revisions"}],"predecessor-version":[{"id":646,"href":"https:\/\/lig-membres.imag.fr\/denisb\/wp-json\/wp\/v2\/posts\/643\/revisions\/646"}],"wp:attachment":[{"href":"https:\/\/lig-membres.imag.fr\/denisb\/wp-json\/wp\/v2\/media?parent=643"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/lig-membres.imag.fr\/denisb\/wp-json\/wp\/v2\/categories?post=643"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/lig-membres.imag.fr\/denisb\/wp-json\/wp\/v2\/tags?post=643"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}