# How many coprimes ?

#### idontknow

How many coprimes are in interval $$\displaystyle [1,100]$$.
method required !

#### Maschke

Is a coprime a composite? That's not a standard term. Two numbers are coprime if the have no common factors, like 25 and 36. The word coprime refers to pairs of integers. Clarify question please.

#### phillip1882

so, a coprime is two numbers that don't share any factors
2 is coprime to 50 numbers between 1 and 100
3 is coprime to 66 numbers between 1 and 100
4 is also coprime to 50 numbers between 1 and 100.
5 is coprime to 80 numbers between 1 and 100.
and so on.

#### skipjack

Forum Staff
The number of coprime pairs of integers, where both integers are in the interval [1, 100] could be counted by a
fairly simple computer program. However, clarification is needed as to whether (1, 2) and (2, 1) should be counted as two pairs or just one.

#### idontknow

composite-primes.

#### skipjack

Forum Staff
Each Integer greater than 1 is either composite or prime (not both). What do you mean?

• idontknow

#### Maschke

composite-primes.
We don't know what you're asking, can you give an example?

Meanwhile the question you don't seem to have intended turns out to be interesting: counting the coprime pairs. I worked out the answer using the inclusion-exclusion principle and got 6231 coprime pairs. Then I wrote a Python program and got 6262 coprime pairs. So I'm close and have an error either in my combinatorics or my code. Getting late so I'll have to wait till tomorrow to resolve the discrepancy.

What I did was to count the number of noncoprime pairs and subtract that from 10,000.
For example if both members of a pair are divisible by 2 that's a noncoprime. For convenience I say "2 divides the pair."

There are 50 even numbers between 1 and 100, computed as 100/2 = 50. All divisions are integer divisions throughout. The number of such pairs is 50^2 = 2500.

Likewise there are 100/3 = 33^2 = 1089 pairs divisible by 3.

But now I've counted pairs like (6,6) twice. I have to subtract off (100/6)^2. Continuing like this I have to subtract off all the pairwise intersections. But if a pair is in a three-fold intersection I've overcounted the subtractions and have to add that one back. This can get confusing but the inclusion-exclusion principle lets you just crank it out using a formula. You take the sum of all the odd-fold intersections (including the original sets of pairs divisible by 2, 3, 5, and 7); minus the sum of all the even-fold pairs.

Gotta go find my 31 pair discrepancy.

(Edit) -- I've got it, small arithmetic mistake. 6262 coprime pairs, computed two different ways, by inclusion-exclusion and by program.

Last edited:
• idontknow

#### idontknow

So how to get number of primes in that given interval ? Method required! (approximations , inequalities ,etc..)

#### skipjack

Forum Staff
My program, which I have confidence in, gives 6087 coprime pairs.

#### Maschke

My program, which I have confidence in, gives 6087 coprime pairs.
Check your program. I got 6262 two different ways: by inclusion-exclusion and via a program.

Edit ... checking my program, doubting my sanity. Anything's possible.

Last edited: