Math Is Fun Forum

  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#1 2006-11-12 20:04:03

maciek
Guest

counting the number of relatively prime

How to count the number of relatively prime
pairs under the given condition?
1<=a<=n 1<=b<=m

#2 2006-11-20 04:30:32

John E. Franklin
Member
Registered: 2005-08-29
Posts: 3,588

Re: counting the number of relatively prime

Wolfram says they are also called "strangers".
Let's just try an example to see where it leads me.
a is equalless than 5
b is equalless than 8
If a is 2, the b could be 3 or 5 or 7.
If a is 3, then b could be 5 or 7 or 8.
If a is 5, then b could be 6 or 7 or 8.
That makes nine.
Sorry, that's all I can figure right now.


igloo myrtilles fourmis

Offline

#3 2006-11-20 04:41:01

mathsyperson
Moderator
Registered: 2005-06-22
Posts: 4,900

Re: counting the number of relatively prime

You've missed a few relatively prime pairs there. There's also (3,4), (4,5) and (4,7), making the total 12.

But I don't think that trying examples like that and trying to spot a pattern will work for this problem. I'll look at it in more detail later on, but I think that there might not be a nice solution in terms of m and n.


Why did the vector cross the road?
It wanted to be normal.

Offline

#4 2006-11-20 04:50:09

pi man
Member
Registered: 2006-07-06
Posts: 251

Re: counting the number of relatively prime

This may help:

http://www.algebra-online.com/relatively-prime-numbers-1.htm

Offline

Board footer

Powered by FluxBB