My Math Forum  

Go Back   My Math Forum > High School Math Forum > Algebra

Algebra Pre-Algebra and Basic Algebra Math Forum


Reply
 
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ón-Sotelo.
leonsotelo is offline  
 
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.
shaggymoods is offline  
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
leonsotelo is offline  
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).
shaggymoods is offline  
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.
skipjack is offline  
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
.
aahanahegde is offline  
Reply

  My Math Forum > High School Math Forum > Algebra

Tags
prime



Search tags for this page
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





Copyright © 2018 My Math Forum. All rights reserved.