Niveau exercices

Divisibilité

Posté par
Eurotruck 25-06-22 à 20:26

Bonjour,

Je reviens avec un exercice qui peut être intéressant.

Parmi les entiers 1,2,3,...,1000 combien divisent la différence $7^{999!}-5^{999!}$ ?

Bon courage

Cordialement

Posté par re : Divisibilité 25-06-22 à 22:12

salut

utilises la formule de aⁿ- ⁿb

Posté par re : Divisibilité 25-06-22 à 22:13

lire aⁿ - bⁿ

Posté par re : Divisibilité 26-06-22 à 10:06

Salut,

Oui et après ?

Cordialement

Posté par re : Divisibilité 26-06-22 à 10:29

Soit $n$ entre $1$ et $1000$
Soit $p = 999! /n$ ; $p$ est un entier.
Si $n<1000$ , c'est évident, et si $n=1000$ aussi.

$7^{999!} = (7^n)^p$
$5^{999!} = (5^n)^p$
$7^{999!}-5^{999!} = (7^n)^p- (5^n)^p =$ ...

Je pense qu'en écrivant ensuite que $7=6+1$ et $5=6-1$ , on arrive à un certain résultat intéressant.

Posté par re : Divisibilité 26-06-22 à 23:10

ty59847 >>>
On arrive à

$((6+1)^n-(6-1)^n)((7^n)^{p-1}+5^n(7^n)^{p-2}+...+(5^n)^{p-1})$
Ensuite $((6+1)^n-(6-1)^n))=\sum_{k=0}^{n}{n\choose k} 6^{k}(1^{n-k}-(-1)^{n-k})$
$=\sum_{k=1}^{2n-1}2{n\choose 2k-1}6^{k}$ ...
Et a partir de la je ne sais pas trop comment avancer...

Posté par re : Divisibilité 28-06-22 à 16:30

J'utiliserais plutôt la formule $a^{\phi(n)} \equiv 1 \pmod{n} \text{ si } pgcd(a,n) = 1$ .

Cliquez pour afficher

Il y a 686 entiers de 1 à 1000 qui sont premiers avec 5 et 7.
Pour ces 686 entiers: $7^{999!} - 5^{999!} \equiv 7^0 - 5^0 \equiv 1 - 1 \equiv 0 \pmod{n}$

Une rapide vérification montre que ce sont bien les seuls:

from operator import mul
from functools import reduce
f = reduce(mul, range(1,1000), 1)
l = [pow(7,f,n) - pow(5,f,n) for n in range(1, 1001)]
l.count(0)
686

La réponse est donc 686.

Posté par re : Divisibilité 28-06-22 à 16:33

Littlefox >>> Félicitations .