MAT246H1 Lecture Notes - Rational Number, Diophantine Equation, Euclidean Algorithm
Document Summary
N=pq, where p and q are big distinct primes. Step 1: find decoder d use euclidean algorithm. Thus the encoded version of the message is 15. Definition 7. 2. 3: a linear diophantine equation is an equation of form for which we seek solutions where x and y are integers. A store sells two different kinds of boxes of candies. One kind sells for a box, another kind for a box. At the end of the day, the store has received . Thus, the store sold 7 of the cheaper boxes and 5 of the more expensive boxes of candy. Theorem 7. 2. 5: the diophantine equation , with a, b and c integers, has integral solutions if and only if divides c. Proof: let and there is a pair of integers satisfying . Part 1: suppose there is an integer solution to the above equation. divides => and divides => By euclidean algorithm, there is s and t satisfying.