Page 2 of 2 FirstFirst 12
Results 16 to 21 of 21

Math Help - Finding prime numbers - problem w/method

  1. #16
    MHF Contributor Quick's Avatar
    Joined
    May 2006
    From
    New England
    Posts
    1,024
    Quote Originally Posted by Euclid Alexandria View Post
    Since 4,753 is a prime number.
    4753\div 7 = 679

    What were you saying
    Follow Math Help Forum on Facebook and Google+

  2. #17
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by Euclid Alexandria View Post
    I was browsing through my subscribed threads for problems that were never completely dealt with. This is one such thread that I'd like to understand. In response to Random's answer (or anyone else reading this), both my book and my previous instructor encouraged the use of calculators for checking answers, but discouraged their use for solving problems. I agree with the idea of not allowing the calculator to do any of my work for me (at this point in time).

    By "the pair," I suppose you're referring to \frac{9,506}{12,222}

    And not \frac{4,753}{6,111}

    Since 4,753 is a prime number.

    Given the restraint of solving by hand, I'm having difficulty determining how I might ascertain the pair's Highest Common Factor... especially if this is the only method available for simplifying this fraction in particular.
    Let me show you my way.

    It is called the "Euclidean Algorithm" (That is you!) and it appears in the Bible of math, "The Elements".

    To begin let me mention some terminology.

    The largest common factor is also called the greatest common divisor.
    It is abbreviated as \gcd

    Say you want to find the greatest common factor of 9506 and 12222. A complicated thing to do, since you need to look at all the factors.

    So we want to know what \gcd(9506,12222)=?

    In order to find that, you need to know what a remainder and a quotient is. The quotient is the integer part when you divide. The remainder is what remains.
    For example, find quotient and remainder when 25 is divided by 6?
    When we divide the integer part that remains is 4. And the remainder is 1.
    Here is the most important step when you get the quotient and remainder you can write,
    25=\underbrace{4}_{\mbox{ Quotient }}\times 6+\underbrace{1}_{\mbox{ Remainder }}
    This is called "Division algorithm".

    Here is another example, express 333 and 110 in division algorithm form?
    333=3\times 110+3
    ---
    Now we can talk about Euclidean Algorithm
    ---
    We start of by expressing 12222 and 9506 in division algorithm form.
    12222=1\times 9506+2716
    According to Euclid this problem of find the greatest common divisor is the same as finding the greatest common divisor between the number to the right of quotient and remainder.
    But to do that
    We need to express 9506 and 2716 in division algorithm form,
    9506=3\times 2716+1358
    Again we find the division algorithm form between number to the right of quotient and remainder,
    2716=2\times 1358+0
    When we reach 0 as remainder this tells us that the number to the right of quotient is the greatest common divisor. So
    \gcd (12222, 9506)=1358
    Follow Math Help Forum on Facebook and Google+

  3. #18
    Junior Member Euclid Alexandria's Avatar
    Joined
    Oct 2005
    From
    Near Dallas, Texas
    Posts
    73

    Question

    Quick, is there an easy way to determine whether a number is divisible by 7?

    PerfectHacker, thank you! That made a lot of sense even at a glance, so it will probably put me at ease this weekend when I look over it in detail. I'm beginning to think this was a really strange problem to appear in my math book. There really are no explanations given for handling its peculiarities.
    Follow Math Help Forum on Facebook and Google+

  4. #19
    Senior Member TriKri's Avatar
    Joined
    Nov 2006
    Posts
    358
    Thanks
    1
    Quote Originally Posted by Euclid Alexandria View Post
    Quick, is there an easy way to determine whether a number is divisible by 7?
    Yes, there is. I'm not Quick, but I hope I can answer anyway!

    Take the last digit and multiply it by 2. So in this case, when you got 2037, the last digit is 7, and multiplied with 2 it's 14. Then you subtract that from "the rest" of the number, which is 203. 203 - 14 = 189. If the new number is divisible by 7, then the original number is as well.

    2037
    203 - 2\cdot 7 = 189
    18 - 2\cdot 9 = 0
    0 is divisible by 7, and so is 2037.[/QUOTE]

    Here's the derivation:

    Consider the number n as a sum of the last digit and the rest of the number, n = 10\cdot x + y.
    We wanna check if n\ \equiv\ 0\ (\text{mod 7})
    10\cdot x + y\ \equiv\ 0\ (\text{mod 7}) \longleftrightarrow
    -10\cdot x - y\ \equiv\ 0\ (\text{mod 7}) \longleftrightarrow /gcd(2, 7) = 1/ \longleftrightarrow (I at least think gcd(2, 7) = 1 is a requirement for using the included \longleftarrow sign)
    2\cdot(-10\cdot x - y)\ \equiv\ 0\ (\text{mod 7}) \longleftrightarrow
    -20\cdot x - 2\cdot y\ \equiv\ 0\ (\text{mod 7}) \longleftrightarrow /-20\ \equiv\ 1\ (\text{mod 7})/ \longleftrightarrow
    x - 2\cdot y\ \equiv\ 0\ (\text{mod 7})
    Last edited by TriKri; December 1st 2006 at 01:58 PM.
    Follow Math Help Forum on Facebook and Google+

  5. #20
    Junior Member Euclid Alexandria's Avatar
    Joined
    Oct 2005
    From
    Near Dallas, Texas
    Posts
    73

    Lightbulb

    Quote Originally Posted by TriKri View Post
    Take the last digit and multiply it by 2. So in this case, when you got 2037, the last digit is 7, and multiplied with 2 it's 14. Then you subtract that from "the rest" of the number, which is 203. 203 - 14 = 189. If the new number is divisible by 7, then the original number is as well.
    Thanks, TriKri, that is a huge help.
    Follow Math Help Forum on Facebook and Google+

  6. #21
    Senior Member TriKri's Avatar
    Joined
    Nov 2006
    Posts
    358
    Thanks
    1
    Your'e so welcome.
    Follow Math Help Forum on Facebook and Google+

Page 2 of 2 FirstFirst 12

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: October 22nd 2011, 12:37 PM
  2. Replies: 8
    Last Post: May 8th 2010, 08:52 AM
  3. Number theory, prime numbers, interesting problem
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: October 21st 2007, 01:23 AM
  4. Prime numbers problem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 11th 2007, 11:05 AM
  5. Replies: 3
    Last Post: September 27th 2007, 04:39 AM

Search Tags


/mathhelpforum @mathhelpforum