programminga general overview oftenn is prime number in that casethere are three important theoremsfirstif is primethen ab (mod nis true if and only if (mod nor (mod nin other wordsif prime number divides product of two numbersit divides at least one of the two numbers secondif is primethen the equation ax (mod nhas unique solution (mod nfor all this solution nis the multiplicative inverse thirdif is primethen the equation (mod nhas either two solutions (mod nfor all nor it has no solutions there are many theorems that apply to modular arithmeticand some of them require extraordinary proofs in number theory we will use modular arithmetic sparinglyand the preceding theorems will suffice the word the two most common ways of proving statements in data-structure analysis are proof by induction and proof by contradiction (and occasionally proof by intimidationused by professors onlythe best way of proving that theorem is false is by exhibiting counterexample proof by induction proof by induction has two standard parts the first step is proving base casethat isestablishing that theorem is true for some small (usually degeneratevalue( )this step is almost always trivial nextan inductive hypothesis is assumed generally this means that the theorem is assumed to be true for all cases up to some limit using this assumptionthe theorem is then shown to be true for the next valuewhich is typically this proves the theorem (as long as is finiteas an examplewe prove that the fibonacci numbersf fi fi- fi- satisfy fi (some definitions have which shifts the series to do thiswe first verify that the theorem is true for the trivial cases it is easy to verify that / and / this proves the basis we assume that the theorem is true for kthis is the inductive hypothesis to prove the theoremwe need to show that fk+ ( / ) + we have fk+ fk fk- by the definitionand we can use the inductive hypothesis on the right-hand sideobtaining fk+ ( / ) ( / ) - ( / )( / ) + ( / ) ( / ) + ( / )( / ) + ( / )( / ) + which simplifies to