
Algebra PreAlgebra and Basic Algebra Math Forum 
 LinkBack  Thread Tools  Display Modes 
January 25th, 2009, 09:38 AM  #1 
Newbie Joined: Mar 2008 Posts: 5 Thanks: 0  Relatively prime
How many positive integers less that 200 are relatively prime to either 15 or 24? Thanks. LeónSotelo. 
January 25th, 2009, 10:25 AM  #2 
Newbie Joined: Jan 2009 From: Baton Rouge, LA Posts: 10 Thanks: 0  Re: Relatively prime
This is a very brute force answer, but hopefully it helps: First off, consider the prime decomposition of 15 and 24: 15 = 3*5 24 = (2^3)*3 Thus all prime numbers less than 200 and not equal to 2,3 or 5 will be relatively prime to either 15 or 24. There are 46 primes < 200 and thus 43 primes that are not 2, 3 or 5. Moreover, as primes generate all integers, we can consider all possible combinations of these primes that are < 200. We have 7^2, 11^2, 13^2, 7*11, 7*13, 7*17, 7*19, 7*23, 11*13, and 11*17. You can check that there are no other combinations that yield values <200. Counting all of this, we see that there are 43+10=53 numbers <200 that are relatively prime to either 15 or 24. There is probably a much simpler and more clever way to find this number, but I'm not sure what it is right now. 
January 25th, 2009, 10:47 AM  #3 
Newbie Joined: Mar 2008 Posts: 5 Thanks: 0  Re: Relatively prime
The official solution is 120 ¿? LeónSotelo 
January 25th, 2009, 11:07 AM  #4 
Newbie Joined: Jan 2009 From: Baton Rouge, LA Posts: 10 Thanks: 0  Re: Relatively prime
I see what happened: I counted the number of integers relatively prime to BOTH. So basically we just need to tweak my methodology: Use similar reasoning to generate all numbers relatively prime to 15 (in this case you can use 2 as a generator), then do the same for 24 (in this case you can use 5). When you are done, be sure to subtract off the number 53 (which will be the number of integers you doublecounted that are relatively prime to both). 
January 25th, 2009, 01:22 PM  #5 
Global Moderator Joined: Dec 2006 Posts: 19,285 Thanks: 1681 
You need to count all the integers less than 200 except for 1, the 66 multiples of 3, and the 13 numbers that are multiples of 10 but not of 3, so the answer is 200  1  66  13 = 120.

July 23rd, 2018, 07:01 AM  #6 
Newbie Joined: Jul 2018 From: india Posts: 1 Thanks: 0 
for both 15 and 24 take the nearest multiple (without introducing new primes) to 200. for 15 it would 15 itself i.e 225 by eulers totient function 225 has 120 coprime integers less than it subtract the 13 numbers b/w 200 and 225 ( 202,203.....) =107 for 24 it is 8 24*8=192 phi(192)=64 plus 193, 197,199 67. total=107+67=174 subtracting 53 common =1211(1 was counted twice) =120 . 

Tags 
prime 
Search tags for this page 
how many positive integers less than 200 are relatively prime to either 15 or 24,how many positive integers relatively prime to 200,how many positive integers less than or equal to 120 are relatively prime to 120,is 24 and 25 relatively prime,how many numbers of 200 are coprime with 10,relative prime to 120
Click on a term to search for related topics.

Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Primorial + prime = prime  momo  Number Theory  4  June 3rd, 2017 03:29 PM 
p is prime if (2p)! mod (p^3) not = 0  Bogauss  Number Theory  13  February 4th, 2011 11:42 AM 
Prime  Sara so  Number Theory  5  December 20th, 2010 10:52 AM 
p prime  Sara so  Number Theory  2  November 13th, 2010 02:51 AM 
If P is prime imply that a is prime  momo  Number Theory  14  September 26th, 2008 07:21 AM 