User Name Remember Me? Password

 Algebra Pre-Algebra and Basic Algebra Math Forum

 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ón-Sotelo. 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ón-Sotelo 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 double-counted that are relatively prime to both). January 25th, 2009, 01:22 PM #5 Global Moderator   Joined: Dec 2006 Posts: 20,968 Thanks: 2216 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 =121-1(1 was counted twice) =120 .  Tags prime ,

,

,

,

,

### relative prime to 120

Click on a term to search for related topics.
 Thread Tools Show Printable Version Email this Page Display Modes Linear Mode Switch to Hybrid Mode Switch to Threaded Mode Similar Threads Thread Thread Starter Forum Replies Last Post momo Number Theory 4 June 3rd, 2017 03:29 PM Bogauss Number Theory 13 February 4th, 2011 11:42 AM Sara so Number Theory 5 December 20th, 2010 10:52 AM Sara so Number Theory 2 November 13th, 2010 02:51 AM momo Number Theory 14 September 26th, 2008 07:21 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top      