document.write( "Question 1160025: If the greatest common divisor of two integers is 1, then we say those two integers are relatively prime to each other, how many even integers which are between 1 and 1000 (including 1 and 1000) and relatively prime to 105? \n" ); document.write( "

Algebra.Com's Answer #783201 by Edwin McCravy(20055) $\"\"$ $\"About$

You can put this solution on YOUR website!

\r\n" );
document.write( "Since 105 written as a product of primes is 3∙5∙7, we want to subtract from the\r\n" );
document.write( "1000 integers between 1 and 1000 (including 1 and 1000), all the multiples of\r\n" );
document.write( "3,5, or 7, for that would remove all integers which have a common divisor with\r\n" );
document.write( "105 other than 1.\r\n" );
document.write( "\r\n" );
document.write( "Since the multiples of these three primes overlap, we must use the \"sieve\"\r\n" );
document.write( "formula (the method of inclusion and exclusion):\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "To find the number of multiples of an integer between 1 and 1000 (including 1\r\n" );
document.write( "and 1000), we divide 1000 by that integer and take only the whole part:\r\n" );
document.write( "\r\n" );
document.write( "1000/3 = 333.3∙∙∙       so N(multiples of 3)         = 333\r\n" );
document.write( "1000/5 = 200            so N(multiples of 5)         = 200\r\n" );
document.write( "1000/7 = 142.8∙∙∙       so N(multiples of 7)         = 142\r\n" );
document.write( "1000/(3×5) = 66.6∙∙∙    so N(multiples of 3×5=15)    = 66\r\n" );
document.write( "1000/(3×7) = 47.6∙∙∙    so N(multiples of 3×7=21)    = 47\r\n" );
document.write( "1000/(5×7) = 28.5∙∙∙    so N(multiples of 5×7=35)    = 28\r\n" );
document.write( "1000/(3×5×7) = 9.5∙∙∙   so N(multiples of 3×5×7=105) = 9  \r\n" );
document.write( "\r\n" );
document.write( "Substituting in the \"sieve\" formula:\r\n" );
document.write( "\r\n" );
document.write( "(333+200+142)-(66+47+28)+(9) = 675-141+9 = 543\r\n" );
document.write( "\r\n" );
document.write( "That's the number of multiples of 3,5 or 7\r\n" );
document.write( "\r\n" );
document.write( "We subtract from the 1000 integers between 1 and 1000 (including 1 and 1000)\r\n" );
document.write( "\r\n" );
document.write( "and get\r\n" );
document.write( "\r\n" );
document.write( "1000 - 543 = 457  <---answer\r\n" );
document.write( "\r\n" );
document.write( "Edwin

\n" ); document.write( "

\n" );