Question

Prove that if 11 divides n with remainder 5, 11 divides n^2 with remainder 6. Find gcd(93, 18), gcd(1353, 205), and gcd(16384, 1900). Prove by induction that for positive integers n, ___.

a) 2n
b) n + 1
c) n^2 + 2n
d) n^2 - 1

Answer 1

To prove that 11 divides n squared with remainder 6 if it divides n with a remainder of 5, we can represent n as 11k + 5 and square it to show that the remainder is 6 when divided by 11. The GCDs for pairs of numbers given are 3 for (93, 18), 1 for (1353, 205), and 64 for (16384, 1900). The induction proof section lacks enough information to provide an answer.

Step-by-step explanation:

To prove that if 11 divides n with remainder 5, then 11 divides n2 with remainder 6, we can use the concept of modular arithmetic. If 11 divides n with remainder 5, then we can express n as 11k + 5 for some integer k. Squaring both sides, we get:

n2 = (11k + 5)2 = 121k2 + 110k + 25 = 11(11k2 + 10k + 2) + 6

This shows that 11 divides n2 and leaves a remainder of 6, proving the initial statement.

Next, to find the greatest common divisor (GCD) of pairs of numbers, we apply the Euclidean algorithm:

• gcd(93, 18) = 3
• gcd(1353, 205) = 1
• gcd(16384, 1900) = 64

Lastly, the information on proving by induction for positive integers n seems incomplete as the statement to be proved is not provided. This section requires additional information to be correctly answered.