MATH 271 Study Guide - Final Guide: Equivalence Class, Euclidean Algorithm
12 May 2014
School
Department
Course
Professor
Document Summary
The marks for each problem are given to the left of the prob- [8] 1. (a) use the euclidean algorithm to nd gcd(100, 57). Also use the algorithm to nd integers x and y such that gcd(100, 57) = 100x + 57y. 2 (b) use part (a) to nd an inverse a for 57 modulo 100 so that 0 a 99; that is, nd an integer a {0, 1, . , 99} so that 57a 1 (mod 100). In this question, you may assume that every integer is either even or odd but not both. But otherwise use no facts about even or odd integers except for the de nition. S be the statement: for all integers a and b, if a is odd and b | a then b is odd. (a) prove that s is true. 4 (b) find and simplify the number of integers a {1, 2, 3, .
