Forum de mathématiques - Bibm@th.net

kadaide

Membre

Inscription : 02-04-2013

Messages : 188

la fonction phi

Bonjour

Phi(n) est le nombre d’entiers compris entre 1 et n-1 et premiers avec n
J’ai démontré dans les questions précédentes :
Pour n>=1: 1<=Phi(n)<=n-1

Pour p premier : Phi(p)=p-1

Phi(p²)=p(p-1)

Pour p premier  et a>0: Phi(p^a)=p^(a-1)*(p-1) que je n’ai pas encore démontré, je la laisse pour après car ce n’est pas facile !

Pour n et m premiers entre eux et a>0:

pgcd(a,n)=1 et pgcd(a,m)=1<=====> pgcd(a,n*m)=1

Voici la question qui me parait un peu floue si j’ose dire :

Pour n et m premiers entre eux,

on note U₁,U₂,…,U_phi(n) tous les entiers entre 1 et n-1 et premiers avec n
V₁,V₂…,V_phi(m) tous les entiers entre 1 et m-1 et  premiers avec m

Montrer que TOUS les entiers compris entre 1 et n*m-1 et premiers avec  n*m sont les entiers U_iV_j
avec 1<=i<=Phi(n) et 1<=j<=Phi(m)

J’ai d’abord abordé cette question par un exemple numérique :
7 et 8 premiers entre eux

Phi(7)=6={1,2,3,4,5}

Phi(8)=4={1,3,5,7}

Phi(7*8)=24={1,3,5,9,11,13,15,17,19,23,25,27,29,31,33,37,39,41,43,45,47,51,53,55}

Je remarque que :

U₃*V₃=15 qui est un élément de la liste de Phi(7*8), c'est bon

Mais  les 24 entiers de la liste de Phi(7*8) ne sont pas TOUS le produit de U_i*V_j, par exemple 11, ce qui me parait contradictoire avec l'énoncé de la question!

Merci pour vos commentaires

Fred

Administrateur

Inscription : 26-09-2005

Messages : 7 352

Re : la fonction phi

Salut,

  Ton contre-exemple est parfait, la propriété qu'on te demande de démontrer est fausse!

Fred.

kadaide

Membre

Inscription : 02-04-2013

Messages : 188

Re : la fonction phi

Bonjour Fred

J'ai pris cet exercice sur un livre de maths terminale S option math (arithmétique)

Ton contre-exemple est parfait, la propriété qu'on te demande de démontrer est fausse!

Mais alors peut être que U_iV_j représente autre chose que le produit U_i*V_j

En principe de cette question on doit déduire que Phi(n*m)=Phi(n)*Phi(m), n et m premiers entre eux.

Ostap Bender

Membre

Inscription : 23-12-2015

Messages : 242

Re : la fonction phi

Bonjour kadaide.

L'égalité [tex] \phi(n*m)=\phi(n)*\phi(m)[/tex], n et m premiers entre eux, est une conséquence du théorème chinois, pas très au programme de TS.

Peux-tu dénoncer le manuel en question ? C'est pour ma collection...

Ostap Bender.

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

Re : la fonction phi

Salut,

théorèmes des restes chinois, non ?

Ostap Bender

Membre

Inscription : 23-12-2015

Messages : 242

Re : la fonction phi

Bonjour Freddy,

Théorème chinois sur un site digne de foi...
mais surement aussi appelé théorème des restes chinois, ailleurs.

Ostap Bender

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

Re : la fonction phi

Re,

vi, sous un autre angle : un autre point de vue

Fred

Administrateur

Inscription : 26-09-2005

Messages : 7 352

Re : la fonction phi

Re-

  Je ne suis pas complètement sûr que l'on ait besoin du théorème chinois, ou de ce qu'il en reste...
Par exemple, avec des probabilités, on peut démontrer presque plus facilement la relation finale. Il faudrait que je réfléchisse 5 minutes pour savoir comment interpréter ceci autrement.

F.

kadaide

Membre

Inscription : 02-04-2013

Messages : 188

Re : la fonction phi

Bonjour Ostap Bender

Le livre: HACHETTE Collection repères  TS Spécialité Dépôt légal 05/2006

Puisqu'ils ont posé la question, on peut penser que c'est possible sans les restes chinois que je ne connais pas.

1<=Phi(n*m)<=n*m-1
On enlève à m*n-1 les multiples de n qui sont au nombre m-1 et les multiples de m qui sont au nombre n-1
Mais avec ça on a pas le compte, il faudra enlever d'autres entiers mais comment ?

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

Re : la fonction phi

Re,

dans le manuel "Arithmétique" de Marc Hindry (C&M, Paris 2008) il est plutôt fait état du lemme chinois.
Tu vois, Fred, il en reste de moins en moins :-)))

Dernière modification par freddy (09-04-2016 09:12:31)