Mark all true statements. Group of answer choices

If a, b, q and r are integers and a = bq + r, then gcd (a, b) = gcd (b, r).

To test whether 101 is prime, you only need to divide it by 2,3,5 and 7.

If it is not divisible by any of those numbers, then it is prime.

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.