Pgcd ?

(Cliquez-ici pour accéder à la version originale de cette discussion avec couleurs et images)





Posted by: poulette

n = 1209516
Trouver le plus grand entier dont le carré est un diviseur de N.




Posted by: yvelines78

bonjour,

1209516/3=403172
403172/2=201586
201586/2=100793
100793/7=14399
14399/7=2057
2057/11=187
187/11=17
17/17=1
1209516=3*2*2*7*7*11*11*17*1

ce serait donc x=2*7*11=154

1209516/154²=51


Posted by: poulette

Merci pour ta réponse Yvelines78.
J'aimerais comprendre (j'ai 30 ans, j'ai arrêté l'école il y a une dizaine d'années donc...) : comment fais tu pour trouver les entiers diviseurs ? Tu prends des chiffres au hasard et tu vois si tu tombes sur un entier ? Il y a une règle simple (j'ai tenté de chercher sur le net, mais n'ai pas trop compris) ? Ce serait sympa de me répondre : je n'aime pas ne rien comprendre !!

merci en tout cas


Posted by: fahr451

bonsoir

il n'y a pas de règle simple
on peut dire certaines choses
divisible par 2 : nombre pair
divisible par 3 : la somme des chiffres est divisible par 3
divisible par 5 : se termine par 0 ou 5
divisible par 9 : somme de chiffres divisible par 9

sinon...


Posted by: Flodelarab

Sinon ....

divisible par 4 si le nombre composé des 2 derniers chiffres est divisible par 4
divisible par 11 si la somme des chiffres de rang pair moins la somme des chiffres de rang impaire est divisible par 11 (on trouve souvent 0. ex: 121; 1234512345)

On peut construire un test simple de divisibilité pour tous les entiers.
Il en existe pour la divisibilité par 7, 13, 17, 19 ...

De manière générale, si tu cherches un diviseur, ne cherches pas ailleurs qu'entre 2 et racine carrée du nombre .... c'est inutile.

Et si tu cherches à factoriser un nombre qui a trop de chiffres .... là tu joues dans la cour des grands et rien est simple comme dit Fahr. Pas de méthode systématique.
Pour les nombres les plus grands, on utilise actuellement les staitistiques et la probabilité d'avoir un diviseur dans une certaine fourchette de nombres ....
Difficile.


Posted by: buzard

Citation:
Posté par Flodelarab
Et si tu cherches à factoriser un nombre qui a trop de chiffres .... là tu joues dans la cour des grands et rien est simple comme dit Fahr. Pas de méthode systématique.


?

pourtant en divisant ton nombre par 2 autant de fois que possible, puis par 3, puis par 5 (les diviseurs premiers) ... On obtient bien une factorisation de ce nombre.

si c'est pas une méthode systématique je me demande bien ce que c'est?


Posted by: Flodelarab

Citation:
Posté par buzard
?

pourtant en divisant ton nombre par 2 autant de fois que possible, puis par 3, puis par 5 (les diviseurs premiers) ... On obtient bien une factorisation de ce nombre.

si c'est pas une méthode systématique je me demande bien ce que c'est?

OK

Et si ton nombre est la multiplication de 2 nombre premiers que tu écrirais en base 10 avec 1000 chiffres, comment fais tu pour trouver la factorisation ? Tu testes tous les nombres premiers jusqu'à racine de ton nombre ?

bon courage.

Mais pour des petits nombres, je suis d'accord avec toi.
De plus, les multiples de 2 couvrent la moitié du champ. Les multiples de 3, le tiers. Les multiples de 5, le cinquieme etc ... il est peu probable de tomber sur un nombre difficile en tirant au hasard. Mais bon. Ce n'est pas systématiquement possible.


Posted by: poulette

En tout cas, je comprends mieux comment arriver à un résultat sans en passer effectivement par la recherche en testant tous les nombres entiers après 2...
Flodelarab et fahr, je vais apprendre par coeur ces petites choses bien logiques mais que j'avais oubliées, ça m'aidera si je tombe dessus au concours.

Merci encore !










-