Bibm@th

Forum de mathématiques - Bibm@th.net

Bienvenue dans les forums du site BibM@th, des forums où on dit Bonjour (Bonsoir), Merci, S'il vous plaît...

Vous n'êtes pas identifié(e).

#1 19-06-2016 15:55:19

Yassine
Membre
Inscription : 09-04-2013
Messages : 975

Petit pb d'arithmétique

Bonjour à tous,
Petit exo récupéré lors des mes balades Internet :

Quels sont les 10 derniers chiffres de l'écriture décimale de 2^(3^(4^(5^(6^(7^(8^9))))))

Réponse sans démonstration pour vérification

8170340352


L'ennui dans ce monde c'est que les idiots sont sûrs d'eux et les gens sensés pleins de doutes. B. Russel

Hors ligne

#2 20-06-2016 05:10:49

freddy
Membre chevronné
Lieu : Paris
Inscription : 27-03-2009
Messages : 6 141

Re : Petit pb d'arithmétique

Salut,

sans avoir regardé,

je trouve, sauf erreur

5035160576

.

On you !


Memento Mori ! ...

Hors ligne

#3 20-06-2016 05:18:04

freddy
Membre chevronné
Lieu : Paris
Inscription : 27-03-2009
Messages : 6 141

Re : Petit pb d'arithmétique

freddy a écrit :

Salut,

sans avoir regardé,

je trouve, sauf erreur

5035160576

.

On you !

Non, je m'y suis mal pris.
I try again ...

Dernière modification par freddy (20-06-2016 05:18:24)


Memento Mori ! ...

Hors ligne

#4 23-06-2016 07:54:30

freddy
Membre chevronné
Lieu : Paris
Inscription : 27-03-2009
Messages : 6 141

Re : Petit pb d'arithmétique

Re,

nouvel essai

a priori

2 096 714 752, sous réserve de vérifications


Memento Mori ! ...

Hors ligne

#5 23-06-2016 09:42:09

Yassine
Membre
Inscription : 09-04-2013
Messages : 975

Re : Petit pb d'arithmétique

@freddy : Nope ! Le résultat n'est pas identique à celui que j'ai. Pourrais-tu donner ta démarche ?
Je décrirai la solution que je connais (qui n'est pas de moi) après.


L'ennui dans ce monde c'est que les idiots sont sûrs d'eux et les gens sensés pleins de doutes. B. Russel

Hors ligne

#6 24-06-2016 06:20:19

freddy
Membre chevronné
Lieu : Paris
Inscription : 27-03-2009
Messages : 6 141

Re : Petit pb d'arithmétique

Re,

laisse moi encore chercher, je ne suis pas un grand spécialiste de ces questions (je suis même un grand ignorant :-)), c'est un petit défi personnel !


Memento Mori ! ...

Hors ligne

#7 24-06-2016 19:31:48

leon1789
Membre
Inscription : 27-08-2015
Messages : 1 200

Re : Petit pb d'arithmétique

Les deux derniers chiffres...
N = 2^(3^(4^x)) mod 100 ?

Texte caché

N = 2^(3^(4^x)) mod 4 = 0
N = 2^(3^(4^x)) mod 25 =  2^(3^(4^x) mod 20 ) = 2^(3^(4^x mod 8)) = 2^(3^0) = 2 ?

donc N = 52 mod 100

Dernière modification par leon1789 (24-06-2016 19:33:25)

Hors ligne

#8 24-06-2016 20:07:19

Yassine
Membre
Inscription : 09-04-2013
Messages : 975

Re : Petit pb d'arithmétique

@leon1789

Pour les passages 2^(3^(4^x)) mod 25 =  2^(3^(4^x) mod 20 )
et 2^(3^(4^x) mod 20 ) = 2^(3^(4^x mod 8)), qu'as tu utilisé comme propriété ?

J'imagine qu'à la fin, tu utilises le théorème des restes chinois.


L'ennui dans ce monde c'est que les idiots sont sûrs d'eux et les gens sensés pleins de doutes. B. Russel

Hors ligne

#9 24-06-2016 20:31:59

leon1789
Membre
Inscription : 27-08-2015
Messages : 1 200

Re : Petit pb d'arithmétique

Hola, top secret !

@Yassine

Pour les passages 2^(3^(4^x)) mod 25 =  2^(3^(4^x) mod 20 )
et 2^(3^(4^x) mod 20 ) = 2^(3^(4^x mod 8)), qu'as tu utilisé comme propriété ?

J'utilise $x^{\phi(n)} = 1 \mod n$ lorsque $pgcd(x,n)=1$ et où $\phi$ est la fonction indicatrice d'Euler ( $\phi(25) = 20$, $\phi(20)=8$ ).

2^20 = 1 mod 25 donc   2^(3^(4^x)) mod 25 = 2^(3^(4^x) mod 20 )
et ensuite 3^(4^x) mod 20 = 3^(4^x mod 8)


Oui, à la fin, théorème chinois avec 4 et 25.

Hors ligne

#10 24-06-2016 20:41:56

Yassine
Membre
Inscription : 09-04-2013
Messages : 975

Re : Petit pb d'arithmétique

@leon1789

Je n'avais pas les yeux en face des trous, j'ai mal calculé $\phi(25)$.
La solution complète utilise également le théorème de Fermat-Euler, tu es sur la bonne voie.


L'ennui dans ce monde c'est que les idiots sont sûrs d'eux et les gens sensés pleins de doutes. B. Russel

Hors ligne

#11 04-07-2016 20:18:56

freddy
Membre chevronné
Lieu : Paris
Inscription : 27-03-2009
Messages : 6 141

Re : Petit pb d'arithmétique

Salut,

nouvel essai, sans regarder la solution.

tentative n°3

8 349 412 352

La méthode sera expliquée plus tard ...


Memento Mori ! ...

Hors ligne

#12 04-07-2016 20:40:24

Yassine
Membre
Inscription : 09-04-2013
Messages : 975

Re : Petit pb d'arithmétique

@freddy : not yet


L'ennui dans ce monde c'est que les idiots sont sûrs d'eux et les gens sensés pleins de doutes. B. Russel

Hors ligne

#13 04-07-2016 20:46:03

freddy
Membre chevronné
Lieu : Paris
Inscription : 27-03-2009
Messages : 6 141

Re : Petit pb d'arithmétique

Je l'aurai, un jour, je l'aurai ... ;-)
J'ai dû m'arrêter trop tôt !


Memento Mori ! ...

Hors ligne

#14 05-07-2016 06:45:09

freddy
Membre chevronné
Lieu : Paris
Inscription : 27-03-2009
Messages : 6 141

Re : Petit pb d'arithmétique

@yassine,

je te propose les 9 premières décimales

essai n° 1 pour 9

170 340 352

Tu achètes ?


Memento Mori ! ...

Hors ligne

#15 05-07-2016 06:47:02

Yassine
Membre
Inscription : 09-04-2013
Messages : 975

Re : Petit pb d'arithmétique

@freddy : Nope !


L'ennui dans ce monde c'est que les idiots sont sûrs d'eux et les gens sensés pleins de doutes. B. Russel

Hors ligne

#16 05-07-2016 07:04:27

freddy
Membre chevronné
Lieu : Paris
Inscription : 27-03-2009
Messages : 6 141

Re : Petit pb d'arithmétique

Re,

à quel rang c'est OK ?


Memento Mori ! ...

Hors ligne

#17 06-07-2016 07:45:14

freddy
Membre chevronné
Lieu : Paris
Inscription : 27-03-2009
Messages : 6 141

Re : Petit pb d'arithmétique

Re,

j'ai regardé la solution : c'est OK avec 9 décimales, yassine est joueur :-)


Memento Mori ! ...

Hors ligne

#18 06-07-2016 09:48:37

Yassine
Membre
Inscription : 09-04-2013
Messages : 975

Re : Petit pb d'arithmétique

freddy a écrit :

Re,

j'ai regardé la solution : c'est OK avec 9 décimales, yassine est joueur :-)

Il est surtout myope !!
C'est un très bon exploit.


L'ennui dans ce monde c'est que les idiots sont sûrs d'eux et les gens sensés pleins de doutes. B. Russel

Hors ligne

#19 06-07-2016 11:21:38

freddy
Membre chevronné
Lieu : Paris
Inscription : 27-03-2009
Messages : 6 141

Re : Petit pb d'arithmétique

Re,

je te pardonne, mon fls. Bon, maintenant, l'Everest : les 10 premières décimales !!!


Memento Mori ! ...

Hors ligne

#20 07-07-2016 05:46:23

freddy
Membre chevronné
Lieu : Paris
Inscription : 27-03-2009
Messages : 6 141

Re : Petit pb d'arithmétique

Re,

les outils de la méthode

L'exponentiation modulaire rapide avec R. Les restes chinois sont moins faciles à manier


Memento Mori ! ...

Hors ligne

#21 17-07-2016 12:54:04

Yassine
Membre
Inscription : 09-04-2013
Messages : 975

Re : Petit pb d'arithmétique

Pour ne pas risquer la guillotine (il y en a qui se reconnaîtront), je publie la solution de ce petit exercice.
Bravo à l'auteur dont je ne connais pas le nom.

Réponse argumentée

On peut d'abord observer les résultats intermédiaires suivants :
$ \begin{align}
5^n &\equiv  5^7 \pmod{2 \times 5^7}  &\forall n \geq 7 \\
4^{n + 2 \times 5^7} &\equiv 4^n \pmod{8 \times 5^8} &\forall n \geq 2 \\
3^{n + 8 \times 5^8} &\equiv 3^n \pmod{4 \times 5^9}  &\forall n \geq 0 \\
2^{n + 4 \times 5^9} &\equiv 2^n \pmod{10^{10}} &\forall n \geq 10
\end{align}$

A l'exception de la première égalité, les autres sont une conséquence du théorème de Fermat-Euler :
$pgcd(x,n)=1 \implies x^{\phi(n)} \equiv 1 \pmod{n}$ où $\phi(n)$ est la fonction indicatrice d'Euler. On utilisera notamment pour la calculer l'identité suivante : si la décomposition en facteurs premiers de $n$ est donnée par $n = \Pi_i p_i^{k_i}$, alors $\phi(n)= \Pi_i (p_i - 1)p_i^{k_i-1}$.
Pour la première identité, elle s'établit directement en remarquant que $5^{n-7}$ est impair.

On pose $n=6^{7^{8^9}}$ qui est manifestement plus grand que $7$

En utilisant la première relation, on a $5^n \equiv 5^7 \pmod{2 \times 5^7 }$
En utilisant la deuxième relation on a $4^{5^n} \equiv 4^{5^7} \pmod{8 \times 5^8} = 390624 \pmod{8 \times 5^8}$
On pourra utiliser la fast-exponentiation pour le calcul. Code Python :

pow(4,5**7,8*5**8))

En utilisant la troisième, on a $3^{4^{5^n}} \equiv 5765981 \pmod{4 \times 5^9}$

pow(3,390624,4*5**9))

Enfin, en utilisant la quatrième, on a $2^{3^{4^{5^n}}} \equiv 8170340352 \pmod{10^{10}}$

pow(2, 5765981, 10**10)

La réponse est donc 8170340352.


L'ennui dans ce monde c'est que les idiots sont sûrs d'eux et les gens sensés pleins de doutes. B. Russel

Hors ligne

#22 18-07-2016 07:08:21

freddy
Membre chevronné
Lieu : Paris
Inscription : 27-03-2009
Messages : 6 141

Re : Petit pb d'arithmétique

Salut,

et hop, je l'ai aussi, enfin !!! Bon, méthode de bourrin, car usage intensif de l'outil informatique, mais résultat tout de même.

On a

8.170.340.352
voir ici pour la méthode de base ! Je peux donner tous les détails des calculs.


Memento Mori ! ...

Hors ligne

#23 18-07-2016 07:33:31

Yassine
Membre
Inscription : 09-04-2013
Messages : 975

Re : Petit pb d'arithmétique

Bravo freddy !


L'ennui dans ce monde c'est que les idiots sont sûrs d'eux et les gens sensés pleins de doutes. B. Russel

Hors ligne

#24 18-07-2016 13:33:04

freddy
Membre chevronné
Lieu : Paris
Inscription : 27-03-2009
Messages : 6 141

Re : Petit pb d'arithmétique

Yassine a écrit :

Bravo freddy !

merci à toi de m'avoir donner un beau petit sujet de réflexion !
Je cherche pour l'autre problème.


Memento Mori ! ...

Hors ligne

#25 19-07-2016 06:37:25

freddy
Membre chevronné
Lieu : Paris
Inscription : 27-03-2009
Messages : 6 141

Re : Petit pb d'arithmétique

Salut,

les étapes et résultats intermédiaires.
Les notations ne sont pas très homogènes, car j'ai fait ces calculs en plusieurs étapes, pas à pas, avec des vérifications nécessaires.

Texte caché

n=11; précision de 11 décimales pour avoir les 10 bonnes premières.

134217728=Mod[8^9,10^n]

16763596801 = Mod[7^134217728,10^n]

Conversion en base 2

IntegerDigits[16763596801,2]

{1,1,1,1,1,0,0,1,1,1,0,0,1,1,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,1}

16763596801 - 2^33-2^32-2^31-2^30-2^29-2^26-2^25-2^24-2^21-2^20-2^13-2^12-2^0 =0

sa13=Mod[Mod[6^2^12,10^11]*Mod[6^2^13,10^11]*6,10^11]=94268676096

sa24=Mod[sa13*Mod[6^2^20,10^11]*Mod[6^2^21,10^11]*Mod[6^2^24,10^11],10^11]=8460527616
sa26=Mod[sa24*Mod[6^2^25,10^11]*Mod[6^2^26,10^11],10^11]=2987063296
sa29=Mod[sa26*Mod[6^2^29,10^11],10^11]=86334611456

a30=Mod[Mod[6^2^29,10^11]*Mod[6^2^29,10^11],10^11]=13491920896

a31=Mod[a30*a30,10^11]=63921442816

a32=Mod[a31*a31,10^11]= 79158009856

a33=Mod[a32*a32,10^11]=62593140736

result=Mod[Mod[sa29*a30,10^11]*Mod[a31*a32,10^11]*a33,10^11]=54204000256


IntegerDigits[54204000256,2]

{1,1,0,0,1,0,0,1,1,1,1,0,1,1,0,0,1,1,1,1,0,1,1,0,1,0,0,0,0,0,0,0,0,0,0,0}

54204000256-2^35-2^34-2^31-2^28-2^27-2^26-2^25-2^23-2^22-2^19-2^18-2^17-2^16-2^14-2^13-2^11=0

sb28=Mod[Mod[Mod[5^2^28,10^11]*Mod[5^2^27,10^11]*Mod[5^2^26,10^11]*
Mod[5^2^25,10^11],10^11]*Mod[Mod[5^2^23,10^11]*
Mod[5^2^22,10^11]*Mod[5^2^19,10^11]*Mod[5^2^18,10^11],10^11]*
Mod[Mod[5^2^17,10^11]*Mod[5^2^17,10^11]*Mod[5^2^16,10^11]*
Mod[5^2^14,10^11]*Mod[5^2^13,10^11]*Mod[5^2^13,10^11],10^11],10^11] = 18212890625

b29=Mod[5^2^29,10^11]=18212890625
b30=Mod[b29*b29,10^11]=18212890625
b31=Mod[b30*b30,10^11]=18212890625
b32=Mod[b31*b31,10^11]=18212890625
b33=Mod[b32*b32,10^11]=18212890625
b34=Mod[b33*b33,10^11]=18212890625
b35=Mod[b34*b34,10^11]=18212890625

sb35=Mod[sb28*b31*b34*b35,10^11]=18212890625

IntegerDigits[18212890625,2]

{1,0,0,0,0,1,1,1,1,0,1,1,0,0,1,0,0,1,0,1,0,1,0,1,0,0,0,0,0,0,0,0,0,0,1}

18212890625-2^34-2^29-2^28-2^27-2^26-2^24-2^23-2^20-2^17-2^15-2^13-2^11-2^0= 0

sc29=Mod[Mod[Mod[4^2^29,10^11]*Mod[4^2^28,10^11]*Mod[4^2^27,10^11]*Mod[4^2^26,10^11]*
Mod[4^2^24,10^11],10^11]*Mod[Mod[4^2^23,10^11]*Mod[4^2^20,10^11]*Mod[4^2^17,10^11]*
Mod[4^2^15,10^11]*Mod[4^2^13,10^11]*Mod[4^2^11,10^11]*4,10^11],10^11]=85560776704

c30=Mod[Mod[4^2^29,10^11]*Mod[4^2^29,10^11],10^11]=55944646656

c31=Mod[c30*c30,10^11]=64691982336

c32=Mod[c31*c31,10^11]=61336016896

c33=Mod[c32*c32,10^11]=66397474816

c34=Mod[c33*c33,10^11]=41354233856

tot34=Mod[sc29*c34,10^11]=18212890624

IntegerDigits[18212890624,2]

{1,0,0,0,0,1,1,1,1,0,1,1,0,0,1,0,0,1,0,1,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0}

18212890624-2^34-2^29-2^28-2^27-2^26-2^24-2^23-2^20-2^17-2^15-2^13-2^11=0

stot29=Mod[Mod[Mod[3^2^29,10^11]*Mod[3^2^28,10^11]*Mod[3^2^27,10^11]*
Mod[3^2^26,10^11]*Mod[3^2^24,10^11],10^11]*Mod[Mod[3^2^23,10^11]*
Mod[3^2^20,10^11]*Mod[3^2^17,10^11]*Mod[3^2^15,10^11]*
Mod[3^2^13,10^11]*Mod[3^2^11,10^11],10^11],10^11]=75161036801

Mod[3^2^29,10^11]=71954749441

Mod[71954749441*71954749441,10^11]=17089812481

Mod[17089812481*17089812481,10^11]=35743375361

Mod[35743375361*35743375361,10^11]=97341880321

Mod[97341880321*97341880321,10^11]=27887063041

Mod[27887063041*27887063041,10^11]=52708167681

Mod[52708167681*75161036801,10^11]=84919828481

IntegerDigits[84919828481,2]

{1,0,0,1,1,1,1,0,0,0,1,0,1,1,0,0,1,1,1,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1}

84919828481-2^36-2^33-2^32-2^31-2^30-2^26-2^24-2^23-2^20-2^19-2^18-2^16-2^15-2^14-2^0=0

Mod[Mod[Mod[2^2^30,10^11]*Mod[2^2^26,10^11]*Mod[2^2^24,10^11]*Mod[2^2^23, 10^11],10^11]*
Mod[Mod[2^2^20,10^11]*Mod[2^2^19,10^11]*Mod[2^2^18,10^11]*
Mod[2^2^16,10^11]*Mod[2^2^15,10^11]*Mod[2^2^14,10^11]*2,10^11],10^11]= 68722624512

puis31= Mod[Mod[2^2^30,10^11]*Mod[2^2^30,10^11],10^11]=55944646656

puis32=Mod[55944646656*55944646656,10^11]=64691982336

puis33=Mod[64691982336*64691982336,10^11]=61336016896

puis34=Mod[61336016896*61336016896,10^11]=66397474816

puis35=Mod[puis34*puis34,10^11]=41354233856

puis36=Mod[puis35*puis35,10^11]=16736628736

result=Mod[68722624512*puis36*puis33*puis32*puis31,10^11]=88.170.340.352


Memento Mori ! ...

Hors ligne

Réponse rapide

Veuillez composer votre message et l'envoyer
Nom (obligatoire)

E-mail (obligatoire)

Message (obligatoire)

Programme anti-spam : Afin de lutter contre le spam, nous vous demandons de bien vouloir répondre à la question suivante. Après inscription sur le site, vous n'aurez plus à répondre à ces questions.

Quel est le troisième mot de cette phrase?

Pied de page des forums