91Ó°ÊÓ

Give an example to show that if \(d\) is not prime and \(n^{2}\) is divisible by \(d\), then \(n\) need not be divisible by \(d\).

Every positive even integer less than 26 can be expressed as a sum of three or fewer perfect squares. (For instance, \(10=1^{2}+3^{2}\) and \(16=4^{2}\).)

For each statement in \(17-28\), determine whether the statement is true or false. Prove the statement directly from the definitions if it is true, and give a counterexample if it is false. The sum of any three consecutive integers is divisible by 3. (Two integers are consecutive if, and only if, one is one more than the other.)

For each integer \(n\) with \(1 \leq n \leq 10, n^{2}-n+11\) is a prime number.

When an integer \(b\) is divided by 12 , the remainder is 5 . What is the remainder when \(8 b\) is divided by \(12 ?\)

For each statement in \(17-28\), determine whether the statement is true or false. Prove the statement directly from the definitions if it is true, and give a counterexample if it is false. A necessary condition for an integer to be divisible by 6 is that it be divisible by 2 .

Consider the statement "For all integers \(n\), if \(n^{2}\) is odd then \(n\) is odd." a. Write what you would suppose and what you would need to show to prove this statement by contradiction. b. Write what you would suppose and what you would nced to show to prove this statement by contraposition.

Prove that for all positive integers \(a\) and \(b, a \mid b\) if, and only if, \(\operatorname{gcd}(a, b)=a\). (Note that to prove " \(A\) if, and only if, \(B, "\) you need to prove "if \(A\) then \(B\) " and "if \(B\) then \(A . "\) ")

Each of the statements in \(20-23\) is true. For each, (a) rewrite the statement using a variable or variables and the form \(V\) if ___ then ___ and (b) write the first sentence of a proof (the "starting point") and the last sentence of a proof (the "conclusion to be shown"). Note that you do not need to understand the statements in order to be able to do these exercises. 20\. For all integers \(m\), if \(m>1\) then \(0<\frac{1}{m}<1\).

Write an algorithm that accepts the numerator and denominator of a fraction as input and produces as output the numerator and denominator of that fraction written in lowest terms. (The algorithm may call upon the Euclidean algorithm as needed.)