Results 1 to 5 of 5

Math Help - eudlidean algorithm,permutation.....

  1. #1
    Member
    Joined
    Jul 2006
    Posts
    95

    eudlidean algorithm,permutation.....

    Hello,
    please try to solve these questions.
    m777
    Attached Files Attached Files
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    10,184
    Thanks
    403
    Awards
    1
    Use the Euclidean Algorithm to find gcd(190, 34).

    Given two integers a and b (a > b) and the equation:
    a = q \cdot b + r
    where q and r are some integers (r < b).

    The Euclidean Algorithm states that
    gcd(a, b) = gcd(b, r)

    So start with a = 190 and b = 34.
    By simple division we can find that:
    190 = 5 \cdot 34 + 20

    Thus gcd(190, 34) = gcd(34, 20).

    Repeating this process on gcd(34, 20):
    34 = 1 \cdot 20 + 14

    So gcd(190, 34) = gcd(34, 20) = gcd(20, 14).

    Continuing:
    20 = 1 \cdot 14 + 6
    gcd(190, 34) = gcd(34, 20) = gcd(20, 14) = gcd(14, 6).

    14 = 2 \cdot 6 + 2
    gcd(190, 34) = gcd(34, 20) = gcd(20, 14) = gcd(14, 6) = gcd(6, 2).

    6 = 3 \cdot 2 + 0

    Now, this means that 2 is a divisor of 6, so we are done:
    gcd(190, 34) = gcd(34, 20) = gcd(20, 14) = gcd(14, 6) = gcd(6, 2) = 2.

    Thus gcd(190, 34) = 2.

    -Dan
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Eater of Worlds
    galactus's Avatar
    Joined
    Jul 2006
    From
    Chaneysville, PA
    Posts
    3,001
    Thanks
    1
    For #1b:

    P(n,r)=\frac{n!}{(n-r)!}

    P(n,4)=\frac{n!}{(n-4)!}

    42P(n,2)=\cdot\frac{n!}{(n-2)!}


    \frac{n!}{(n-4)!}=42\frac{n!}{(n-2)!}

    Using the definition of factorial, we can cancel terms in the denomiantors:

    \frac{n!}{(n-4)!}=\frac{n(n-1)(n-2)(n-3)(n-4)....}{(n-4)(n-5)(n-6)(n-7)....} =n(n-1)(n-2)(n-3)=n^{4}-6n^{3}+11n^{2}-6n

    Do the same for the other and we get 42n(n-1)

    We have: n^{4}-6n^{3}+11n^{2}-6n=42n^{2}-42n

    Which gives: n^{4}-6n^{3}-31n^{2}+36n=0

    n(n-9)(n-1)(n+4)

    Which gives :  n=0, \;\ 9, \;\ 1, \;\ -4

    One of these is your answer. I would think it's 9.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,862
    Thanks
    743
    Hello, m777!

    1(a) Use the Euclidean Algorithm to find \text{gcd}(190,34)

    I was taught this way . . .

    [1] Divide the larger by the smaller; note the remainder.
    [2] Divide the remainder into the divisor; note the remainder.
    [3] Repeat step 2 until the remainder is 0.
    [4] The \text{gcd} is the last divisor.
    Code:
            5           1          1         2        3
         ------      ----       ----      ----      ---
      34 ) 190    20 ) 34    14 ) 20    6 ) 14    2 ) 6
           170         20         14        12    ↑   6
           ---        ---        ---       ---       --
            20         14          6         2        0

    Therefore: . \text{gcd}(190,34) \:=\:2



    1(b) Find n if: P(n,4) \:=\:42\!\cdot\!P(n,2)

    We have: . \frac{n!}{(n-4)!} \:=\;42\!\cdot\!\frac{n!}{(n-2)!} \quad\Rightarrow\quad \frac{1}{(n-4)!} \:= \:\frac{42}{(n-2)!}\quad\Rightarrow\quad (n-2)! \:=\:42(n-4)!


    Divide by (n-4)!\!:\;\;(n-2)(n-3) \:=\:42\quad\Rightarrow\quad n^2 - 5n - 36 \:= \:0

    The quadratic factors: . (n + 4)(n - 9) \:=\:0
    . . and has two solutions: . n \:=\:-4,\:9

    Since n must be positive, the answer is: . \boxed{n \,= \,9}



    2. A computer access code consists of from one to three letters
    . . of the English alphabet with repetition allowed.
    How many different code words are possible?

    Since each code letter has 26 choices,
    . . there are: .  26 \times 26 \times 26 \:=\:17,576 possible code words.



    3(a) A box contains 10 different colored light bulbs.
    Find the number of ordered samples of size 3 with replacement.

    The first can be any of the 10 bulbs.
    The second can be any of the 10 bulbs.
    The third can be any of the 10 bulbs.

    There are: . 10 \times 10 \times 10 \:=\:1,\!000 possible ordered samples.



    3(b) How many possible outcomes are there when a fair coin is tossed three times?

    The first toss has 2 possible outcomes (Heads or Tails).
    The second toss has 2 possible outcomes.
    The third toss has 2 possible outcomes.

    There are: . 2 \times 2 \times 2 \:=\:8 possible outcomes.



    4. How many 2-permutations are there of \{w,x,y,z\}? .Write them all.

    There are: . P(4,2) \:=\:12 permutations.

    They are: . \begin{Bmatrix}wx & wy & wz \\ xw & xy & xz \\ yw & yx & yz \\ zw & zx & zy\end{Bmatrix}

    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Jul 2006
    Posts
    95

    excellent.........

    Hello soroban,
    you are genius.
    from
    m777
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. permutation
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: August 2nd 2010, 08:28 AM
  2. Why permutation ?
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: July 11th 2010, 12:27 PM
  3. permutation help
    Posted in the Discrete Math Forum
    Replies: 12
    Last Post: July 9th 2010, 03:37 PM
  4. Permutation-1
    Posted in the Algebra Forum
    Replies: 2
    Last Post: January 18th 2010, 06:04 AM
  5. Permutation
    Posted in the Advanced Algebra Forum
    Replies: 6
    Last Post: May 30th 2009, 01:31 PM

Search Tags


/mathhelpforum @mathhelpforum