Q4. Show that log n! is (n log n). Explain. Q5. Prove that the grade school method of multiplication in Section 1.1.2) when applied to binary numbers is "correct, it always gives the right answer. Q6. Using the definition of 1 = y mod N, justify the rule I = l' mod N, y = y' mod N = TXI' = y x y' mod N Q8. Give an "efficient method to compute the nth Fibonacci number Fn mod N for fixed N. Explain the method and analyze the running time. Also comment on the correctness of the method. Q10. Prove of disprove, if a has an inverse modulo N then N has an inverse modulo a. Q12. Give an efficient" algorithm to compute the least common multiple of two n bit numbers a, b. What is the running time of your algorithm as a function of n