Bon, ok, la magie n'existe pas, tout le monde sait ça: y'a forcément un truc. Donc votre boulot, ça sera d'expliquer ce truc !

Un truc bien connu pour savoir si un nombre est un multiple de 9: on additionne les chiffres de notre nombre. Un peu d'arithmétique prouve ce résultat sans trop de souci. Mais pour autre chose que 9, on fait comment ?
Magie magie: soit un nombre N premier avec 10 (autrement dit, N finit par 1, 3, 7 ou 9)
On définit le nombre D comme ceci:
> Si N finit par 1: N = 10a+1
Alors D = 9a+1
> Si N finit par 3: N = 10a+3
Alors D = 3a+1
> Si N finit par 7: N = 10a+7
Alors D = 7a+5
>Enfin, si N finit par 9: N = 10a+9
Alors D = a+1

Enfin, dans tous les cas, si D > N/2, on peut tout aussi bien prendre D' = D-N, le but étant d'avoir D le plus petit possible en valeur absolue pour faire des calculs simples.
Ayant trouvé ce nombre D, on se pose la question: un nombre P est-il divisible par N? La réponse est oui si et seulement si P sans son dernier chiffre + D * le dernier chiffre de P est divisible par N.
Autrement dit, si P = 10a+b avec 0<=b<=9, alors P est un multiple de N si et seulement si a+D*b est un multiple de N. Magique !

Exemple: Je cherche les multiples de N = 89. D = 9
109826 est un multiple de 89 si et seulement si
10982 + 6*9 = 11036 est un multiple de 89 si et seulement si
1103 + 6*9 = 1157 est un multiple de 89 si et seulement si
115 + 7*9 = 178 est un multiple de 89 si et seulement si
17 + 8*9 = 89 est un multiple de 89, ce qui est vrai (109826 = 1234*89)

374962 est un multiple de 89 si et seulement si
37496 + 2*9 = 37514 est un multiple de 89 si et seulement si
3751 + 4*9 = 3787 est un multiple de 89 si et seulement si
378 + 7*9 = 441 est un multiple de 89 si et seulement si
44 + 1*9 = 53 est un multiple de 89, ce qui est faux (374962 modulo 89 = 5)

Le dernier exemple montre un truc important: on se fiche de savoir la valeur de P % N, uniquement de savoir si c'est 0 ou pas.

A vous de jouer