Arithmetique-trouver le dernier chiffre

[Anonyme]

Bonjour,

cela concerne les exos dans lesquels on demande de trouver le dernier chiffre
d'un gros nombre dans une base.

Par exemple le dernier chiffre du nombre 7^7^7 dans la base décimale.
Pour le trouver on voit que le héros va être 7, on fait la div eucli des
puissances de 7 par 10 avec les congruences, on tombe sur une puissance qui
fait que 7^p=1[10]
ici 7^4=1[10] qui rend l'affaire possible car 1 a la vertu d'être l'element
neutre pour la multiplication. on prouve ensuite que 7^7 est impair puis
toujours avec les congruences on trouve que le dernier chiffre est 3.

J'aimerai maintenant généraliser le probleme:

tous les nombres sauf mention contraire sont dans N*.
Je prend un nombre n s'ecrivant dans une base q( pas forcément décimale donc),
la question est: est ce qu'on trouvera toujours un nombre p tel qu'on ait
n^p=1[q] ?

en regardant les petites valeurs de n, on s'aperçoit vite que pour n=1 cela
marche car 1^(n'importe quoi)=1=q*0+1
mais pour n=2 il ne suffit pas seulement que 2^p=qk+1, avec qk impair. q etant
donné, il n'est pas evident de trouver k tel que 2^p=qk+1.

pensez vous que ce pb peut se generaliser?

merci

[Anonyme]

Wenceslas écrivait :
> est ce qu'on trouvera toujours un nombre p tel qu'on ait n^p=1[q] ?

Ben avec la base q=10, et n=2, on voit pas bien que ça marche pas.

2^p étant pair non divisible par 5 son dernier chiffre va être
2,4,6 ou 8.

--
Michel [overdose@alussinan.org]

[Anonyme]

>J'aimerai maintenant généraliser le probleme:
>
>tous les nombres sauf mention contraire sont dans N*.
>Je prend un nombre n s'ecrivant dans une base q( pas forcément décimale donc),
>la question est: est ce qu'on trouvera toujours un nombre p tel qu'on ait
>n^p=1[q] ?
si gcd(n,q) = 1, la réponse est oui (p = phi(q), fermat). si n et q
ont un diviseur commun autre que 1, elle est non.

Lukas Reck

[Anonyme]

>J'aimerai maintenant généraliser le probleme:[color=green]
>>
>>tous les nombres sauf mention contraire sont dans N*.
>>Je prend un nombre n s'ecrivant dans une base q( pas forcément décimale
>donc),
>>la question est: est ce qu'on trouvera toujours un nombre p tel qu'on ait
>>n^p=1[q] ?
>si gcd(n,q) = 1, la réponse est oui (p = phi(q), fermat). si n et q
>ont un diviseur commun autre que 1, elle est non.
>[/color]

je ne comprends pas qu'il suffit d'avoir gcd(n,q) = 1. Néanmoins il est vrai
que si q est premier, alors cela marche car d'apres le theoreme d'Euler,
n^phi(p)=1[p]. Cependant c'est qu'une implication, donc ne se generalise pas.

[Anonyme]

Wenceslas écrivait :

> je ne comprends pas qu'il suffit d'avoir gcd(n,q) = 1.

pgcd(n,q)=1 bien entendu, enfin je pense qu'il n'y a pas confusion.

> Néanmoins
> il est vrai que si q est premier, alors cela marche car d'apres
> le theoreme d'Euler, n^phi(p)=1[p]. Cependant c'est qu'une
> implication, donc ne se generalise pas.

Le théorème d'Euler dit que si pgcd(n,q)=1 alors a^phi(q)=1[q].
où phi est l'indicatrice d'Euler.
Il n'y a pas besoin de l'hypothèse q nombre premier. Tu peux le
vérifier dans un bouquin.

Tu mélanges peut-être un peu avec le petit théorème de Fermat, qui
est un cas particulier de ce théorème. En effet, avec q nombre
premier tu as phi(q)=q-1.


--
Michel [overdose@alussinan.org]

[Anonyme]

Michel écrivait :

> Le théorème d'Euler dit que si pgcd(n,q)=1 alors a^phi(q)=1[q].

n^phi(q)=1[q] pardon.



--
Michel [overdose@alussinan.org]

[Anonyme]

>> Le théorème d'Euler dit que si pgcd(n,q)=1 alors a^phi(q)=1[q].
>
>n^phi(q)=1[q] pardon.

en effet, j'ai un peu melangé les pinceaux.

maintenant si je prends le pb à l'envers, etant donné un couple (n,q) tel qu'on
ait pas pgcd(n,q)=1, a t on une methode generale au probleme?

[Anonyme]

Wenceslas écrivait :

> maintenant si je prends le pb à l'envers, etant donné un couple
> (n,q) tel qu'on ait pas pgcd(n,q)=1, a t on une methode generale
> au probleme?

Tu veux n^p = qk+1. Et on a pgcd(n,q)|n donc
pgcd(n,q)|n^p et pgcd(n,q)|q

donc pgcd(n,q)| (n^p-qk)=1

C'est une condition nécessaire pour avoir le reste 1 modulo q.

--
Michel [overdose@alussinan.org]