Forum Graph100

Il suffit de s'intéresser au reste de la division entiere grace au modulo "%":
par exemple pour 10/4 la division réelle vaut 2.5, la division entière vaut 2 et le modulo = 10%4 = 10-2*4 = 2. Comme le modulo, donc le reste de la division n'est pas nul, cela signifie que 10 n'était pas divisible par 4

moi j'aurais fait un truc du genre
# define reste(a,b) a - b* (a/b)

ca a l'air de marcher..
par contre c'est vrai que les congruences ( ) c'est plus simple

aaaaaaaaaaaah la la les congruences
Fabuleux outil, fabuleux.

Démontrez moi que 1981^1981 est divisible par 13 !!

Lol
sa me rapelle vaguement quelque chose ^^

_____________
(600ème mess)

bah étant donné que 1981 n'est pas divisible par 13, 1981^1981 n'est pas divisible par 13 !

Ca c toi qui le dis :?

ben facile pour prouver ca, c'est la programme de terminal S....
mais bon c trop loin pour moi :-)
mais je sais qu'un jour je savais le faire....

je l'ai fait l'an dernier en dut, pour le décodage RSA, mais c'est trop loin aussi......

Et non, 1981^1981 n'est pas divisble par 13...

la technique consiste à se ramener à une expression plus simple de 1981^1981, afin d'utiliser des congruences plus simples !!

On remarque d'abord que:

5^0 = 1 [13]
5^1 = 5 [13]
5^1 = 12 [13]
5^3 = 8 [13]
5^4 = 1 [13]

On se demande alors si ça serait pas périodique !!
Une très simple démo par récurrence utilisant les congruences ci dessus suffit à démontrer que pour tout n dans N, on a:

5^(4n) = 1 [13]
5^(4n+1) = 5 [13]
5^(4n+2) = 12 [13]
5^(4n+3) = 8 [13]

Une fois qu'on a ce résultat, on peut alors poser la division euclidienne de 1981 par 4, comme ça on aura la puissance 1981^x = 1981^1981 avec x sous la forme 4k+r:

1981 = 4 * 495 + 1 = 4k+1 (k=495)

De même avec 13, pour avoir x^1981 sous une forme simplifiée en fonction de 13 (+ simple pour la congruence)

1981 = 13 * 152 + 5

Finalement, un nb étant congru à lui mm modulo n, on a:

1981 = 13 * 152 + 5 [13] <=> 1981 = 0 * 152 +5 [13] (revoyez vos congruences si vous comprenez pas la simplification)

Finalement: 1981 = 5 [13]

Donc 1981^1981 = 5^1981 [13] <=> 1981^1981 = 5^(4n+1) [13] <=> 1981^1981 = 5 [13]

Donc c'est pas divisble et le reste est 5!!

ben c'est ta démo qui est fausse !
1981=5 [13]
donc 1981^1981=5^1981 [13]

or 1981=4k+1 donc 5^1981=5 [13] (d'apres ce que tu as démontré)
donc 1981^1981= 5 [13]
donc c'est pas divisible par 13 !
je vais essayer de voir ce qui va pas dans ta démo parce que j'ai pas tres bien compris la fin...

EDIT : c'est cette ligne qui est fausse :

1981^1981 - 5 = 5^(4k+1) - 5^1 [13] <=> 1981^1981 = 1 - 1 [13] <=> 1981^1981 = 0 [13] 

1981^1981-5=5^(4k+1) - 5^1 [13] donc
1981^1981-5=5-5 [13]   (5^(4k+1) est congru a 5 modulo 13)
donc 1981^1981-5=0 [13] !!!!

lol mdr vous avez posté pdt que je corrigeais
merci

j'ai donc viré le faux contre exemple car effectivement 4 n'est pas premier, comment j'ai pu donner un contre exemple qui ne respecte même pas les hypothèses de départ ?!! :mrgreen: y'a des fois vraiment ...

edit:

en fait c'est en démontrant ce qu'à dit overlord que j'ai saisi ma merde lol (je crois que y'a eu une embrouille au niveau de l'énoncé dont je ne me souvenais pas bien, j'ai dû oublier le -5 lol)

Dire que j'ai voulu remettre en cause les dires de mon vénéré maître absolu de tous les temps, le grand le sublime l'incontourable Gauss !! :ptdr:

donc en fait la démo de l'élévation à une certaine puissance ça se ferait du genre:

p premier et ne divisant pas n.

On veut démontrer que p ne divise pas n^m, on va passer par la contraposée. On fait donc:

p|n^m <=> p|(n*n^(m-1)) <=> p|(n^m-1) d'après le théorème de Gauss

Par itération on se retrouve au final avec p|1, or p pas hypothèse est premier, donc la contraposée et fausse et l'implication dans l'autre sens est démontrée

Merci Overlord

oula j'ai pas tres bien compris la seconde démonstartion (mais je connais pas encore le théoréme de gauss ca doit jouer un peu lol)
mais bon comme disait julien je vais te faire confiance !

Exactement, j'ai voulu me pencher plus rigoureusement sur ce qu'ont dit overlord et madjar.
C'est à dire comme tu l'as redit, passer par la contraposée

Et le théorème de gauss que j'utilise n'est pas celui des potentiels hein :mrgreen:

non celui qui dit que:

si a divise bc, et que a est premier avec b, cela implique que a divise c !! (Ce qui en soi est intuitif)

Donc lorsque j'ai réécrit n^m, j'ai dit que c'était n*n^(m-1), or par hypothèse, p ne divise pas n, mais p divise n^m, donc p divise n^(m-1), et ainsi de suite, jusqu'à tomber sur p divise n^0 => p divise 1 donc p = 1 or c'est absurde car p est premier par hypothèse !