Divisibilité...

[Ellyana]

Bonjour,
Je suis en train de travailler sur un exo d'olympiade (2014, Bordeaux, nombres sphéniques et nombres abondants).
Et comme c'était le sujet de 2014, ils se sont amusés à demander si 2014 était sphé***** (comprendre : 2014 a-t-il au moins 3 diviseurs autres que 1 et lui-même ?).
Bien sûr, ce qui saute aux yeux, c'est que 2014=1007*2
Mais ensuite, 1007 est-il premier ? La réponse est non, 1007=19*53.

Je me pose la question : Etant donné que l'on n'est pas censé avoir de calculette le jour des olympiades (il me semble), comment peut-on deviner que 1007 est divisible par 19 ? On est vraiment obligé de tester tous les nombres premiers jusqu'à 31 ? (parce que 32²=1024) C'est-il pas un peu long ?

Et question subsidiaire : Le nombre 2015 a-t-il des propriétés particulières ? (parce que je sens qu'on va faire des choses avec ce nombre cette année, soit au kangourou soit aux olympiades. Et puis, même pour ma culture personnelle...)
Si quelqu'un pouvait me répondre,
Ella'.

[Luc]

Bonjour,
Je suis en train de travailler sur un exo d'olympiade (2014, Bordeaux, nombres sphéniques et nombres abondants).
Et comme c'était le sujet de 2014, ils se sont amusés à demander si 2014 était sphé***** (comprendre : 2014 a-t-il au moins 3 diviseurs autres que 1 et lui-même ?).
Bien sûr, ce qui saute aux yeux, c'est que 2014=1007*2
Mais ensuite, 1007 est-il premier ? La réponse est non, 1007=19*53.

Je me pose la question : Etant donné que l'on n'est pas censé avoir de calculette le jour des olympiades (il me semble), comment peut-on deviner que 1007 est divisible par 19 ? On est vraiment obligé de tester tous les nombres premiers jusqu'à 31 ? (parce que 32²=1024) C'est-il pas un peu long ?

Et question subsidiaire : Le nombre 2015 a-t-il des propriétés particulières ? (parce que je sens qu'on va faire des choses avec ce nombre cette année, soit au kangourou soit aux olympiades. Et puis, même pour ma culture personnelle...)
Si quelqu'un pouvait me répondre,
Ella'.

Pour savoir que 1007=19*53, il y a le crible d'Eratosthène qui est comme tu as dit le test des nombres premiers, mais on a besoin de tester que jusqu'à 19. Ensuite avec le chiffre des unités tu peux limiter le nombre de tests par exemple pour 13, les seuls nombres à tester se finissent par 9, pour 17 les nombres à tester se finissent par 1, etc.

Il y a des test de primalité plus efficaces que le crible d'Eratosthène, mais c'est plus compliqué (ils utilisent les congruences)
Luc

[Ellyana]

Bonjour Luc
En fait j'ai une méthode qui me parait un brin différente, parfois elle marche super bien, parfois elle est plus longue, mais j'y suis habituée.
Pour vois si 1007 est divisible par 7 (par exemple), je soustrais 100*7, soit 700, à 1007, ce qui me donne 307. Si 1007 est divisible par 7, 307 l'est aussi, et 1007/7 = 307/7 + 100
Je soustrais encore 7*40, soit 280, ce qui me donne 27. 27 n'est pas divisible par 7, donc 1007 ne l'est pas.

Pour 1007/19, c'est un peu plus compliqué, parce que la table de 19 est plus dure...
1007-19*50 = 1007-950 = 57 /// 57-3*19=0
Donc 1007 = 19 * (50+3)

C'est quoi les congruences ?

[Sa Majesté]

Salut

Au lieu de soustraire 700, tu peux te contenter de soustraire 7.
Si 1007 est divisible par 7 alors 1007-7=1000 aussi, ce qui n'est manifestement pas le cas.

Pour 19, tu as 19x3=57 donc si 1007 est divisible par 19 alors 1007-57=950 aussi et donc 95 aussi ce qui est le cas.

[nodjim]

Pour le test de primalité pour les nombres jusqu'à 10000: 1007 est impair, j'ôte 7 reste 1000, pas divisible par 7 car divisible par 2 et 5 uniquement. Pour la division par 11, c'est facile. Par 13, je fais 1007+13=1020--->102-->51 pas divisible par 13.
Pour 17 1007-17=1000-10=990--->99 pas divisible par 17.
Pour 19 je fais 1007-57(3*19)=1000-50=950---->95=5*19, 1007 divisible par 19.
Avec de l'exercice on le fait mentalement.

[Ellyana]

D'accord. Une astuce consiste à simplifier un nombre, pas forcément en le réduisant jusqu'à ce qu'il ait deux chiffres comme je l'ai fait, mais en se débrouillant pour qu'il ait d'autres diviseurs, ce qui le simplifie plus rapidement (oui, ma manière d'expliquer n'est pas très correcte, je sais ^^)

C'est ça, les congruences ?

[WillyCagnes]

bjr

Divisibilité par 19

Un entier a est divisible par 19 si et seulement si le nombre obtenu en additionnant le double de son chiffre des unités au nombre formé des autres chiffres est divisible par 19.

Démonstration

a = 10b + a0, où a0 est son chiffre des unités et b le nombre formé par ses autres chiffres.

Remarquons que a = 0 (mod 19) si et seulement si 2a = 0 (mod 19).

Or, 2a = 20b + 2a0 = b + 2a0 (mod 19).

Ainsi, a = 0 (mod 19) si et seulement si b + 2a0 est divisible par 19.


voir ces liens
https://www.gyyv.vd.ch/branches/mathematique/nombres/textes/dem_div19.htm

http://fr.wikipedia.org/wiki/Liste_de_crit%C3%A8res_de_divisibilit%C3%A9#Lemme_de_divisibilit.C3.A9_par_19

[Luc]

D'accord. Une astuce consiste à simplifier un nombre, pas forcément en le réduisant jusqu'à ce qu'il ait deux chiffres comme je l'ai fait, mais en se débrouillant pour qu'il ait d'autres diviseurs, ce qui le simplifie plus rapidement (oui, ma manière d'expliquer n'est pas très correcte, je sais ^^)

C'est ça, les congruences ?

Les congruences c'est transformer l'arithmétique habituelle faite sur la droite des nombres entiers, en l'arithmétique modulaire faite sur un cercle autour duquel on enroule cette droite. Quand deux nombres de la droite correspondent au même point du cercle, on dit qu'ils sont congrus modulo la longueur du cercle.

Par exemple, modulo 12, les entiers 3, 15, 27, -9, etc. sont tous congrus à 3 modulo 12. En particulier, on peut donc compter de 1 à 12 (ou de 0 à 11) et recommencer une fois qu'on a fait un tour complet : c'est comme ça qu'une horloge mesure le temps.

La relation de divisibilité s'interprète très facilement par des congruences : a divise b si et seulement si b est congru à 0 modulo a. Autrement dit, quand on divise b par a, le reste de la division euclidienne est 0.
Les congruences permettent par exemple de justifier pourquoi la "preuve par 9" fonctionne (exercice!).

Luc

[Ellyana]

Okayyyyy !
Donc en gros, le cercle trigonométrique que l'on voit, avec pi/2, pi, 3pi/2, c'est un cas particulier de congruence !
Merci Luc ! =D