Question

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.

Answer 1

True

False

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.