Dénombrement

 Niveau exercicesPartager :
			        
Dénombrement
Posté par 
flight  28-03-26 à 10:39
Bonjour  , je vous propose l'exercice suivant pour vous amuser ... pas dur :

On considère un entier N 16.

Déterminer le nombre d'entiers k tels que :

16 kN  et   pgcd(k,15) = 1.
 Posté par 
dpire : Dénombrement  28-03-26 à 12:03
Bonjour,

 Cliquez pour afficher
Les premiers par définition  et ceux qui ne sont multiples ni de 3 ni de 5 .le nombre de premiers n'est  pas formulable 

Je trouve  |N/3| pour N<50
 Posté par 
sanantonio312re : Dénombrement  28-03-26 à 12:24
Bonjour,

Mon axe de recherche:
 Cliquez pour afficher
Soit n3 le nombre de multiples de 3, n5 le nombre de multiples de 5 et n15 celui des multiples de 15.

Le nombre recherché est N-15-n3-n5+n15

Je n'ai plus qu'à exprimer des trois ni en fonction de N 
 Posté par 
sanantonio312re : Dénombrement  28-03-26 à 12:33
Finalement, je trouve
 Cliquez pour afficher

Qu'il est sans doute possible de simplifier
 Posté par 
flightre : Dénombrement  28-03-26 à 17:54
Bonne expression de sanantonio312
 Posté par 
dpire : Dénombrement  29-03-26 à 09:30
Bonjour,

Par définition ,les entiers premiers  sont à compter et je vois  mal comment les inclure dans k .
 Posté par 
candide2re : Dénombrement  29-03-26 à 10:11
Bonjour,

Une démo :

PGCD(k,15) = 1 signifie que k n'est ni divisible par 3 ni divisible par 5.

****

Recherche du nombre d'entiers de 1 à N premiers avec 15 :

Tous : N

Multiple de 3 : E(N/3) (avec E() pour partie entière).

Multiple de 5 : E(N/5)

Multiple de 15 : E(N/15)

--> N - E(N/3) - E(N/5) + E(N/15)    (1)

 (car les multiples de 15 on été inclus dans ceux à la fois multiples de 3 et de  5)

****

Recherche du nombre d'entiers de 1 à 15 premiers avec 15 :

1,2,4,7,8,11,13,14 ---> Il y en a 8   (2)

*****

Total cherché = (1) - (2)

Total cherché =  N - E(N/3) - E(N/5) + E(N/15) - 8
 Posté par 
dpire : Dénombrement  29-03-26 à 16:35
Ce que je veux dire c'est que 8 est calculé en observant (1 à 15 ) dans le cas de N16

Imaginons le même exercice avec N>100 ,les premiers  perturbent

le calcul ...
 Posté par 
dpire : Dénombrement  29-03-26 à 16:45
Je veux dire si on remplace 16 par 100 soit  100kN
 Posté par 
candide2re : Dénombrement  29-03-26 à 18:55
dpi @ 29-03-2026 à 16:35

Ce que je veux dire c'est que 8 est calculé en observant (1 à 15 ) dans le cas de N16

Imaginons le même exercice avec N>100 ,les premiers  perturbent

le calcul ...

Bonjour,

Il n'y a pas de problème.

Avec l'énoncé : 

On considère un entier N >= 100.

Déterminer le nombre d'entiers k tels que :

100 <= k <= N  et   pgcd(k,100) = 1.

*********************

100 = 2^2 * 5^2

PGCD(k,100) = 1 signifie que k n'est ni divisible par 2 ni divisible par 5.

****

Recherche du nombre d'entiers de 1 à N premiers avec 100 :

Tous : N

Multiples de 2 : E(N/2) (avec E() pour partie entière).

Multiples de 5 : E(N/5)

Multiples de 10 : E(N/10)

--> N - E(N/2) - E(N/5) + E(N/10)  (car les multiples de 10 ont été inclus dans ceux à la fois multiples de 2 et de  5)

****

Recherche du nombre d'entiers de 1 à 99 premiers avec 100 :

99 - E(99/2) - E(99/5) + E(99/10) = 99 - 49 - 19  + 9 = 40   (2)

*****

Total cherché = (1) - (2)

Total cherché =  N - E(N/2) - E(N/5) + E(N/10) - 40
  Posté par 
dpire : Dénombrement  30-03-26 à 08:27
Merci

Depuis le début ,j'étais obsédé par les premiers.Or si on enlève de N les multiples concernés , les autres nombres y compris les premiers sont solution.