Facebook Page
Twitter
RSS
+ Reply to Thread
Results 1 to 5 of 5
  1. MHB Master
    MHB Site Helper
    MHB Math Helper
    evinda's Avatar
    Status
    Offline
    Join Date
    Apr 2013
    Posts
    3,256
    Thanks
    3,213 times
    Thanked
    972 times
    Awards
    MHB Model User Award (2016)  

MHB Model User Award (2014)
    #1
    Hello!!!

    I am looking at the following exercise:


    Let $b=r_0, r_1, r_2, \dots$ be the successive remainders in the Euclidean algorithm applied to $a$ and $b$. Show that after every two steps, the remainder is reduced by at least one half. In other words, verify that $$r_{i+2}< \frac{1}{2} r_i \ ,\text{ for every } i=0,1,2, \dots$$


    Conclude that the Euclidean algorithm terminates in at most $2 \log_2{(b)}$ steps, where $\log_{2}$ is the logarithm to the base $2$. In particular, show that the number of steps is at most seven times the number of digits in $b$. [ Hint: What is the value of $\log_2{10}$ ?]

    I have tried the following:

    The general formula for $r_{i-1}$ in the Euclidean algorithm is the following:

    $$r_{i-1}=q_{i+1} r_i+r_{i+1}$$


    So we have: $r_i=q_{i+2} r_{i+1}+r_{i+2} \\=q_{i+2}(q_{i+3} r_{i+2}+r_{i+3})+r_{i+2} \\=q_{i+2} q_{i+3} r_{i+2} +q_{i+2} r_{i+3}+r_{i+2}\\ \geq r_{i+2}+q_{i+2} r_{i+3}+r_{i+2} \\=2r_{i+2}+q_{i+2} r_{i+3}> 2r_{i+2}$

    So it follows that $r_{i+2}<\frac{1}{2} r_i$.

    As for the number of steps, I have thought the following:


    We have that $b=r_0>2r_2> 4r_4>8r_6> \dots> 2^m r_{2m}$

    The Euclidean algorithm terminates when we find a remainder that is equal to zero.

    So we check when $r_{2m}<1$.

    $r_{2m}<1 \Rightarrow 2^m r_{2m}<2^m$.

    We also have that $2^m r_{2m}<b$.

    But from these two inequalities, we cannot find a relation between $m$ and $b$, can we?

  2. MHB Oldtimer
    MHB Site Helper
    MHB Math Scholar
    Opalg's Avatar
    Status
    Offline
    Join Date
    Feb 2012
    Location
    Leeds, UK
    Posts
    2,225
    Thanks
    756 times
    Thanked
    6,158 times
    Thank/Post
    2.768
    Awards
    Graduate POTW Award (2016)  

MHB Analysis Award (2016)  

Graduate POTW Award (2015)  

Graduate POTW Award (Jul-Dec 2013)  

MHB Pre-University Math Award (Jul-Dec 2013)
    #2
    Quote Originally Posted by evinda View Post
    We also have that $2^m r_{2m}<b$.
    Take logs to base 2 in that inequality: $m + \log_2 r_{2m} < \log_2b$.

    If $m > \log_2b$ then $\log_2 r_{2m} < \log_2b - m < 0$. So $r_{2m}<1$, which means that $r_{2m} =0$, and the algorithm has terminated.

    Since $m > \log_2b\ \Longrightarrow\ 2m > 2\log_2b$, this shows that as soon as the algorithm reaches the $2m$th step, with $2m > 2\log_2b$, the algorithm will terminate.

  3. MHB Master
    MHB Site Helper
    MHB Math Scholar

    Status
    Offline
    Join Date
    Jan 2012
    Posts
    2,280
    Thanks
    514 times
    Thanked
    4,176 times
    Thank/Post
    1.832
    Awards
    MHB Chat Room Award (2016)  

MHB Humor Award (2016)  

MHB Discrete Mathematics Award (2016)  

MHB Best Ideas Award (2015)  

MHB Discrete Mathematics Award (2015)
    #3
    The fact that $r_i>2r_{i+2}$ can be shown slightly more easily. We have $r_i>r_{i+1}$ for all $i$ because $r_{i+1}$ is the remainder when something (namely, $r_{i-1}$) is divided by $r_i$. So we have
    \[
    r_i=q_{i+2}r_{i+1}+r_{i+2}\ge r_{i+1}+r_{i+2}>2r_{i+2}.
    \]

  4. MHB Master
    MHB Site Helper
    MHB Math Helper
    evinda's Avatar
    Status
    Offline
    Join Date
    Apr 2013
    Posts
    3,256
    Thanks
    3,213 times
    Thanked
    972 times
    Awards
    MHB Model User Award (2016)  

MHB Model User Award (2014)
    #4 Thread Author
    Quote Originally Posted by Evgeny.Makarov View Post
    The fact that $r_i>2r_{i+2}$ can be shown slightly more easily. We have $r_i>r_{i+1}$ for all $i$ because $r_{i+1}$ is the remainder when something (namely, $r_{i-1}$) is divided by $r_i$. So we have
    \[
    r_i=q_{i+2}r_{i+1}+r_{i+2}\ge r_{i+1}+r_{i+2}>2r_{i+2}.
    \]
    Yes, I see...

  5. MHB Master
    MHB Site Helper
    MHB Math Helper
    evinda's Avatar
    Status
    Offline
    Join Date
    Apr 2013
    Posts
    3,256
    Thanks
    3,213 times
    Thanked
    972 times
    Awards
    MHB Model User Award (2016)  

MHB Model User Award (2014)
    #5 Thread Author
    Quote Originally Posted by Opalg View Post
    Take logs to base 2 in that inequality: $m + \log_2 r_{2m} < \log_2b$.

    If $m > \log_2b$ then $\log_2 r_{2m} < \log_2b - m < 0$. So $r_{2m}<1$, which means that $r_{2m} =0$, and the algorithm has terminated.

    Since $m > \log_2b\ \Longrightarrow\ 2m > 2\log_2b$, this shows that as soon as the algorithm reaches the $2m$th step, with $2m > 2\log_2b$, the algorithm will terminate.
    I understand... So the algorithm terminates in at least $2\log_2b$ steps, or not?

    In order to show that the number of steps is at least seven times the number of digits in $b$, we use the fact that


    $$2\log_2b=2\log_2{10} \cdot \log_{10}{b} \approx 6.6 \log_{10}{b}$$

    Right?

Similar Threads

  1. Replies: 1
    Last Post: September 19th, 2015, 08:28
  2. Replies: 4
    Last Post: January 1st, 2015, 23:46
  3. Get the right answer but intermediate steps may be wrong
    By find_the_fun in forum Differential Equations
    Replies: 1
    Last Post: September 24th, 2014, 23:20
  4. [SOLVED] Laplace Transform with two steps
    By dwsmith in forum Differential Equations
    Replies: 2
    Last Post: January 26th, 2014, 22:11
  5. Replies: 9
    Last Post: February 2nd, 2012, 13:38

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
Math Help Boards