| Summary: | In this chapter we study the basic properties of the divisibility of integer numbers and the time of execution of theirs elementary arithmetical operations. More precisely, we begin from the Euclidean division, we prove the unicity of g-adic expansion of an integer<br/>(where g is a fixe positive number) and we introduce the notion of the length of an integer. Next, we deal with the notion<br/>of binary digital operation, we compute the number of binary digital operation needed for the execution of elementary arithmetical operations and we introduce the reader to the algorithms and theirs running time. We give examples of elementary algorithms and the Karatsuba algorithm for fast integer multiplication. We introduce the notions of greatest common divisor and the least common multiple of two integers and we give theirs basic properties. Furthermore, we present the extended Euclidean algorithm and we compute its running time. Finally, we study the solvability of the linear Diophantine equation.
|
|---|
