Todai Entrance Exam: Subject 2015 – Problem 3

(1)

    \[ q = x + 6, r = -3 \]

(2)

    \[ (a) : r - \frac{LT(r)}{LT(g)}g \]

(3)

We see that g = LT(g) + g' and r_{k} = LT(r_{k}) + r_{k}' with \text{deg}(g') < \text{deg}(g) and \text{deg}(r_{k}') < \text{deg}(r_{k}). After each iteration, \text{deg}(r) decreases by 1 as:

    \[ r_{k} = r_{k-1} - \frac{LT(r_{k-1})}{LT(g)}g = r_{k-1} - \frac{LT(r_{k-1})}{LT(g)}(LT(g) + g') = r_{k-1} - LT(r_{k-1}) - \frac{LT(r_{k-1})}{LT(g)}g' \]

So the algorithm in (2) will eventually terminate as \text{deg}(g) is still the same while \text{deg}(r) keep decreasing after each iteration.

(4)

    \[ GCD(f, g) = GCD(f - qg, g) = GCD(r, g) = GCD(r, g - q_{2}r) = GCD(r, r_{2}) = ... (*) \]

If we continue that loop, eventually one of the function parameters will be zero. So:

    \[ (b) : s \]

    \[ (c) : rem \]

(5)

The upper bound of number of times that a function remainder is called inside the while-loop during the calculation of GCD(f, g) is \min(m, n). It is easy to see from (*) that after one iteration r is less than g one degree (remember \deg{r} < \deg(g) \leq \deg(f), and one iteration later r_{2} is less than r one degree, and this pattern will keep up until one of the inputs are 0 (degree 0), that is after \min(m, n) iterations.

Note: I’m not sure if I’m correct. Reference for the worst-case scenario in real number.


Facebooktwittergoogle_plusredditpinterestlinkedinmail

Leave a Reply

Your email address will not be published. Required fields are marked *