Question

Mark all true statements. Group of answer choices

Answer 1

Answer:

True

False

Step-by-step explanation:

a) The first statement is the basis for Euclid's algorithm to compute the gcd of two nonnegative integers a,b. You can prove this as follows.

Let G=gcd(a,b). Since r=a-bq and G divides a and G divides b, then G divides r. Now, G divides a and G divides r, hence G divides gcd(b,r).

On the other hand, since a=bq+r, and gcd(b,r) divides b and r, then gcd(b,r) divides a. Therefore gcd(b,r) divides a and b, which implies that gcd(b,r) divides G.

x divides y and y divides x implies that |x|=|y|. The GCD's are nonnegative, therefore G=gcd(b,r).

b) It is false. In general, to test for primality of N, you have to check that all primes smaller than N do not divide N. In this case, we have to check for 2,3,5,7,11,13,17,19,23,...

101 is prime, but this may be false in general. For example, consider N=13*11=143. N is not prime, and n is not divisible by 2,3,5, or 7.