Astuce de divisibilité

[jwtdd]

Bonjour,
Je cherche à généraliser "l'astuce" de divisibilité par 7 tel que décrit là: http://www.johndcook.com/blog/2010/10/27/divisibility-by-7/

c'est à dire (du moins se que j'en ais compris):
soit n=10a + b
(10a+b) modulo 7 = (10a+b -3.7.b) modulo 7

10a+b -3.7.b = 10a+b -21b = 10a-20b = 10(a-2b)

(10a+b) modulo 7 = 10(a-2b) modulo 7
or 7 ne divise pas 10,
alors 7 divise 10a+b si et seulement si 7 divise a-2b.


j'essai de généraliser avec B à la place de 10 et un diviseur c:

soit a,b,c et B des entiers, c ne divisant pas B
soit x tel que x.c-1 soit divisible par B

(a.B+b) modulo c = (a.B +b -x.b.c ) modulo c (puisque l'on ne fait que soustraire un multiple de c)
(a.B+b) modulo c = (a.B +(-x.b.c +b)) modulo c
(a.B+b) modulo c = (a.B +(b(-x.c +1))) modulo c
(a.B+b) modulo c = (a.B -(b( x.c -1))) modulo c

après factorisation
(a.B+b) modulo c = B(a - (x.c-1).b/B) modulo c

soit y=(x.c-1)/B
(a.B+b) modulo c = B(a - y.b) modulo c
or c ne divise pas B donc
c divise (a.B+b) si et seulement si c divise (a-y.b)

J'ais eu mon bac S il y a 9 ans il ne me reste que quelque bribes..., est-ce se que j'ais écrit semble correcte?
Si c'est correcte y a t'il un algorithme ou un théorème permettant de trouver efficacement un entier
x tel que x.c-1 soit divisible par B ?

[chan79]

salut
j'ai simplement regardé pour la divisibilité par 31

10n+u= 0 (31) ssi n-3u=0 (31)

2635 se scinde en 263 et 5
263-3*5=248
24-3*8=0 donc 2635 divisible par 31

2759
275-27=248
24-24=0 donc 2759 divisible par 31


démo (modulo 31)
si 10n+u=0, alors 3u=-30n=-30n+31n=n donc n-3u=0
si n-3u=0 alors 10n=30u=30u-31u=-u donc 10n+u=0

ce critère n'est pas très intéressant pour les grands nombres

à voir pour 41
10n+u= 0 (41) ssi n-4u=0 (41)

[jwtdd]

Merci chan79, petite typo 2759->5759, j'ais cru que c’était un contre exemple.

C'est dans une base différente que j'espère rendre intéressant,
plus particulièrement en base 2^64 puisque la bibliothèque GMP stock les nombres dans plusieurs entiers non signé de 64bits.
Transformer des divisions euclidiennes+additions en un même nombre de multiplication+soustraction devrait économiser pas mal de temps si le nombre à tester est très très grand.
Bon j'en suis pas encore là, la complexité semble être transféré au calcul des "formules magiques" jusqu'à la racine carré du nombre qui devront toute être stockées, je compte sur le fait que les calculs peuvent être fait une fois pour toute.

J'ais deux craintes:
- cette formule magique n'existe pas pour tout les nombres premiers
- une méthode brut de recherche de ces formules prendrait beaucoup trop de de temps

EDIT:
J'ais repris ton idée de partir de Y pour retrouver le diviseur, du coup sa devient trivial

(x.diviseur-1)%Base = 0
(x.diviseur-1)/Base = y
x=(y*Base+1)/diviseur


((y*Base+1)/diviseur) doit être entier , donc avec diviseur=(y*Base+1), ((y*Base+1)/diviseur) est toujours entier

(1*10 + 1)/11
(2*10 + 1)/21
>(2*10 + 1)/3
>(2*10 + 1)/7
(3*10 + 1)/31
(4*10 + 1)/41
(5*10 + 1)/51
>(5*10 + 1)/3
>(5*10 + 1)/17
(6*10 + 1)/61
(7*10 + 1)/71
(8*10 + 1)/81
>(8*10 + 1)/3
(9*10 + 1)/91
>(9*10 + 1)/7
>(9*10 + 1)/13
(11*10 + 1)/111
>(11*10 + 1)/3
>(11*10 + 1)/37

On trouve des tests un peu dans le désordre mais c'est pas grave il y a de quoi mettre ça sous forme d'algorithme et laisser mon ami l'ordinateur trier et verifier :D.