Ask Question
10 November, 22:46

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.

+3
Answers (1)
  1. 11 November, 01:29
    0
    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.
Know the Answer?
Not Sure About the Answer?
Get an answer to your 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 ...” in 📙 Mathematics if there is no answer or all answers are wrong, use a search bar and try to find the answer among similar questions.
Search for Other Answers