CS 173 Study Guide - Final Guide: Euclidean Algorithm, Pseudocode

• School: University of Illinois
• Department: Computer Science
• Course: CS 173
• Professor: All

Document Summary

Claim: for all non-zero integers a and b, if a | b and b | a, then a = b: (6 points) use the euclidean algorithm to compute gcd(2015, 837). Two positive integers p and q are relatively prime if and only if gcd(p, q) > 1. true false. Claim: for all positive integers a, b, and c, if gcd(a, b) = n and gcd(a, c) = p, then gcd(a, bc) = np: (6 points) use the euclidean algorithm to compute gcd(1609, 563). For any positive integers p and q, if lcm(p, q) = pq, then p and q are relatively prime. true false (5 5) 1 (mod 6) true false. Claim: for all positive integers a, b, and c, gcd(ca, cb) = c gcd(a, b: (6 points) use the euclidean algorithm to compute gcd(2380, 391). Two positive integers p and q are relatively prime if and only if gcd(p, q) = 1. true false.