Mpsi - arithmétique

[Anonyme]

Bonjour,

Je bloque complètement sur cet exo :

Soit D un entier premier à 10. On cherche à construire un critère de
divisibilité par D.

1) Justifier l'existence d'un entier F tel que 10F + 1 soit divisible par
D. On choisit un tel entier D et on appelle N le quotient.

2) Soit n un entier, que l'on écrit sous la forme n = 10q + r avec q,r in Z
(en général, q et r sont le quotient et le reste dans la division par 10,
mais ce n'est pas indispensable). On fdéfinit l'entier n' par n'= q - rF.
a) Vérifier que n' = DNq - Fn.
b) En déduire que Dn' est divisible par D ssi n l'est.
c) Proposer un algorithme pour tester la divisibilité d’un entier n par D
(sous la forme : « tant que ... faire ... »).

3. On prend dans cette question F = 1. Par quel entier D peut-on tester la
divisibilité ?

4. On prend maintenant F = 2.
a) Par quels entiers D peut-on tester la divisibilité ?
b) Dans le cas de la divisibilité par 3, justifier que l’on a même n'
congru à n [3].

5. Quelle valeur choisir pour F pour obtenir un test de divisibilité par 13
?
Présenter les calculs effectués par l'algorithme pour tester la
divisibilité de 12 542 598 874 par 13 (on pourra remarquer, pour effectuer
à la main des calculs simples, que q - 9r = q + r - 10r).

Je bloque en fait à la première déjà... Si quelqu'un peut me mettre sur la
voie...

Merci d'avance !!

[Anonyme]

Boil wrote:
> Bonjour,
>
> Je bloque complètement sur cet exo :
>
> Soit D un entier premier à 10. On cherche à construire un critère de
> divisibilité par D.
>
> 1) Justifier l'existence d'un entier F tel que 10F + 1 soit divisible par
> D. On choisit un tel entier D et on appelle N le quotient.
^^^^^ F ?
pgcd(10, D) = ?

que dit M. Bezout ?

[Anonyme]

Bonjour,

> 1) Justifier l'existence d'un entier F tel que 10F + 1 soit divisible par
> D. On choisit un tel entier D et on appelle N le quotient.

Modulo D, 10 est inversible, c'est a dire qu'il existe f tel que
10 * f = 1 [D]. Non ? Si oui, ca marche presque, mais pas tout a fait
puisque ca nous donne 10f-1 = 0 [D] c'est a dire 10f-1 divisible par D ....

> 2) Soit n un entier, que l'on écrit sous la forme n = 10q + r avec q,r in Z
> (en général, q et r sont le quotient et le reste dans la division par 10,
> mais ce n'est pas indispensable). On définit l'entier n' par n'= q - rF.
> a) Vérifier que n' = DNq - Fn.
> b) En déduire que Dn' est divisible par D ssi n l'est.
^^^
le D est de trop : c'est n' seulement

Un tres bel exercice. Et sur des mathematiques assez recentes !

A plus, peut etre
Amities,
Olivier

[Anonyme]

Olivier wrote:

> Un tres bel exercice. Et sur des mathematiques assez recentes !

Récentes ?

Peux-tu préciser ?

[Anonyme]

> Récentes ?
>
> Peux-tu préciser ?

Pas vraiment, j'ai perdu la référence ...
Je me souviens d'un article d'il ya quelques
années ou

"
Justifier l'existence d'un entier F tel que 10F + 1 soit divisible par D.
"

etait simplement remplace par 10F + A
et ou la question de determiner les "bons" F et A
etait abordee .... Comme on va vouloir elever
-F a des puissances modulo D, il vaut mieux
qu'il ait peu de puissances differentes et que ces
puissances soient "simples" (par exemple pour un
critere de divisibilite par 23 ...).
Il y a eu pas mal de litterature sur la question ces
dernieres années, rien de bien fantastique souvent,
mais la question semble revenir au gout du jour
et il y a parfois des choses assez jolies.

Voila, desole pour ma memoire defaillante !
Ou alors c'est mon disque qui a perdu le fichier :-!
Amities,
Olivier

[Anonyme]

Salut, merci de ta précieuse aide, j'ai essayé de chercher la suite mais je
n'arrive pas trop à faire les questions 4 et 5. Est-ce que vous pourriez
m'expliquer ?

[Anonyme]

Matryce wrote:
> Salut, merci de ta précieuse aide, j'ai essayé de chercher la suite mais je
> n'arrive pas trop à faire les questions 4 et 5. Est-ce que vous pourriez
> m'expliquer ?

Qu'est-ce qui cloche, précisément ?