document.write( "<A HREF=/cgi-bin/jump-to-question.mpl?question=1197060>Question 1197060</A>: <I><SPAN STYLE=\"word-break: break-all;\"> There are 1859 balls inside an urn from 1 to 1859. A ball is selected randomly. What is the probability that the selected ball has a number that is relatively prime to 1859?<BR>\n" );
document.write( " </SPAN>\n" );
document.write( "</I><HR><TABLE width=100%><TR><TD><B><A HREF=http://www.algebra.com/>Algebra.Com's</A> Answer #830173 by </B><A HREF=/tutors/aboutme.mpl?userid=math_tutor2020><B>math_tutor2020(3817)</B></A><img src=\"/images/stars/stars-13.gif\" alt=\"\" >&nbsp;<A HREF=/tutors/aboutme.mpl?userid=math_tutor2020><IMG SRC=http://www.algebra.com/images/aboutme-small.gif BORDER=0 alt=\"About Me\" VALIGN=MIDDLE></A>&nbsp;<IMG SRC=http://www.algebra.com/images/nopicture.jpg><BR>You can <A HREF=\"/cgi-bin/embed-solution.mpl?show=1&solution=830173\">put this solution on YOUR website!</A><BR><SPAN STYLE=\"word-break: break-all;\"> <font color=black size=3><BR>\n" );
document.write( "Two numbers are relatively prime, aka coprime, if the only factor they have in common is 1.<BR>\n" );
document.write( "In other words, if the GCF is 1, then the numbers are coprime.<BR>\n" );
document.write( "Example: 15 and 34 are relatively prime\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "Determine the prime factorization of 1859<BR>\n" );
document.write( "1859 = 11*13*13 = 11*13^2\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "If an integer x is coprime with 1859, then it won't have any of 11 or 13 as part of its factorization.<BR>\n" );
document.write( "If x is not coprime with 1859, then it will have at least one or more of the factors mentioned.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "set A = multiples of 11, from 11 to 1859<BR>\n" );
document.write( "set B = multiples of 13, from 13 to 1859<BR>\n" );
document.write( "set C = multiples of 11*13, from 143 to 1859<BR>\n" );
document.write( "11*13 = 143 is the LCM of 11 and 13\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "A = {11*1, 11*2, 11*3, ..., 11*169}<BR>\n" );
document.write( "B = {13*1, 13*2, 13*3, ..., 13*143}<BR>\n" );
document.write( "C = {11*13*1, 11*13*2, 11*13*3, ..., 11*13*13} = {143*1, 143*2, 143*3, ..., 143*13}\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "Claim1: C is a subset of A, and C is a subset of B<BR>\n" );
document.write( "Claim2: All values in sets A,B,C are not relatively prime to 1859<BR>\n" );
document.write( "Claim3: All values in sets A,B,C consist of all non-relatively prime values from 11 to 1859<BR>\n" );
document.write( "I'll let the student prove these claims.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "There are 169 items in set A<BR>\n" );
document.write( "There are 143 items in set B<BR>\n" );
document.write( "That's 169+143 = 312 values<BR>\n" );
document.write( "But as the claim1 mentions, C is a subset of A and B. <BR>\n" );
document.write( "In other words, A and B have an overlap of values which reside in set C<BR>\n" );
document.write( "Each item in set C is of the form 11*13*m where m ranges from m = 1 to m = 13.<BR>\n" );
document.write( "Set C has 13 items inside it\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "Subtract 13 from 312 to find the number of unique items in either set A or set B or both<BR>\n" );
document.write( "312 - 13 = 299<BR>\n" );
document.write( "There are 299 values that aren't relatively prime to 1859, and these values go from 11 to 1859.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "Think of it like this<BR>\n" );
document.write( "n(A or B) = n(A) + n(B) - n(A and B)<BR>\n" );
document.write( "n(A or B) = 169 + 143 - 13<BR>\n" );
document.write( "n(A or B) = 299<BR>\n" );
document.write( "There are 299 values in set A, set B, or both\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "Since there are 299 values that aren't relatively prime with 1859, this means there must be 1859-299 = 1560 items that are relatively prime to 1859.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "Side note:<BR>\n" );
document.write( "The totient function counts how many values are relatively prime to n, where we go from 1 to n<BR>\n" );
document.write( "Typing \"totient(1859)\", without quotes, into WolframAlpha gets us the result 1560<BR>\n" );
document.write( "<a  rel=nofollow HREF= \"https://www.wolframalpha.com/input?i=totient%281859%29\">https://www.wolframalpha.com/input?i=totient%281859%29</a><BR>\n" );
document.write( "Here's an article talking about the totient function in more detail<BR>\n" );
document.write( "<a  rel=nofollow HREF= \"https://mathworld.wolfram.com/TotientFunction.html\">https://mathworld.wolfram.com/TotientFunction.html</a><BR>\n" );
document.write( "The formula to calculating totient(1859) is to compute <IMG STYLE=\"max-width:80%;\" SRC=/cgi-bin/plot-formula.mpl?expression=1859%2A%281-1%2F%28p%5B1%5D%29%29%2A%281-1%2F%28p%5B2%5D%29%29 ALIGN=MIDDLE  ALT=\"1859%2A%281-1%2F%28p%5B1%5D%29%29%2A%281-1%2F%28p%5B2%5D%29%29\"   DISABLED_style= \"max-width:90%; height:auto;\" > where <IMG STYLE=\"max-width:80%;\" SRC=/cgi-bin/plot-formula.mpl?expression=p%5B1%5D ALIGN=MIDDLE  ALT=\"p%5B1%5D\"   DISABLED_style= \"max-width:90%; height:auto;\" > and <IMG STYLE=\"max-width:80%;\" SRC=/cgi-bin/plot-formula.mpl?expression=p%5B2%5D ALIGN=MIDDLE  ALT=\"p%5B2%5D\"   DISABLED_style= \"max-width:90%; height:auto;\" > are the prime factors 11 and 13 in this case. Which means we have totient(1859) = <IMG STYLE=\"max-width:80%;\" SRC=/cgi-bin/plot-formula.mpl?expression=1859%2A%281-1%2F11%29%2A%281-1%2F13%29+=+1560 ALIGN=MIDDLE  ALT=\"1859%2A%281-1%2F11%29%2A%281-1%2F13%29+=+1560\"   DISABLED_style= \"max-width:90%; height:auto;\" >\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "So we have 1560 relatively prime values we want out of 1859 values total in {1,2,3,...,1858,1859}<BR>\n" );
document.write( "The probability we're after is 1560/1859 = (13*120)/(13*143) = <font color=red>120/143</font>\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "Answer = <font color=red>120/143</font><BR>\n" );
document.write( "</font> </SPAN>\n" );
document.write( "</TD></TR></TABLE>\n" );