Midterm II solutions

Problem 1 (10 points)

Find the number of -digit binary numbers (the number of digits should be considered in base ). Write the answer in binary as well.

Solution

Let’s try to find the largest -digit binary number. It is . The smallest -digit binary number is . Therefore, the number of -digit binary numbers is .

We could also perform the same calculation in decimal notation for more clarity. The largest -digit binary number is . The smallest -digit binary number is . Therefore, the number of -digit binary numbers is .

Problem 2 (10 points)

Prove that the number is divisible by for any base and any base digits and .

Solution

Let’s denote and . Then, . At the same time, . Therefore, , so is divisible by .

Problem 3 (20 points)

Define , , and for . Prove that for every positive integer , .

Prove that for every positive integer , .

Solution

We will prove the first equality by induction. The base case is trivial. Assume that the equality holds for . Then, we have

We want to prove that

We know that , so

which completes the induction.

We will prove the second equality by induction as well. The base case is trivial. Assume that the equality holds for . Then, we have

We want to prove that

Using the induction assumption,

which completes the induction.

Problem 4 (20 points)

Find the GCD of and .

Does the equation have solutions? If so, find one.

Solve the congruence .

Solution

We will use the Euclidean algorithm to find the GCD of and :

Therefore, .

The equation has solutions due to Bezout’s lemma since . We can find the solutions inversing the Euclidean algorithm procedure:

Therefore, and is a solution to the equation .

To solve the congruence , we can use the solution to the equation . We have , so is the inverse of modulo . Therefore, the solution to the congruence is or .

Problem 5 (20 points)

Propose a conversion procedure from base to base that would work efficiently for large numbers. Prove its validity. Convert the number to base .

Solution

To convert a number from base to base , we can group the binary digits in groups of starting from the right. If the number of digits is not a multiple of , we can add leading zeros. Then, we can convert each group of binary digits to a single hexadecimal digit.

More precisely, a number written in base can be represented as . Grouping the binary digits in groups of starting from the right and factoring out the corresponding power of gives: . Then, we can convert each group of binary digits to a single hexadecimal digit.

Let’s convert the number to base . We group the binary digits in groups of starting from the right: . Then, we convert each group of binary digits to a single hexadecimal digit: .

Problem 6 (20 points)

Solve the following equation in the set of integers:

Solution

The left part of the equation can be factored as , and is therefore divisible by . Let us consider the equation modulo :

Equivalently, . Let us enumerate which remainders can square numbers have modulo :

Therefore, the equation has no solutions, and the original equation has no solutions in the set of integers.

Problem 7 (25 points)

Let and be positive integers. Prove that

if and only if one of or divides the other.

Solution

Let denote the greatest common divisor of and . Then, and for some positive integers and . The least common multiple of and is . Therefore, the inequality is equivalent to , or . Then , or . The only way this inequality can hold is if or . When , divides , and when , divides . Therefore, the inequality holds if and only if one of or divides the other.

Problem 8 (25 points)

Given a number written in base devise a divisibility criterion for and . Prove their validity.

Check whether the number is divisible by and . (Partial score will be attributed for answering the last question without the divisibility criterion.)

Solution

Consider a number written in base : . Then .

Let’s observe that and . Therefore, and . Therefore, is divisible by if and only if is divisible by , and is divisible by if and only if is divisible by . is divisible by iff .

In other words, a number written in base is divisible by if and only if its last digit is , , or , and it is divisible by if and only if the sum of its digits is divisible by .

The number is not divisible by since is not divisible by . The number is divisible by since the sum of its digits is , which is divisible by .

Problem 9 (25 points)

Show that is divisible by for any positive integer .

Solution 1 (induction)

We will prove the statement by induction. The base case is true since is divisible by . Assume that the statement is true for . Then, we have

for some integer . We want to prove that the statement is true for . We have

which is divisible by . Therefore, the statement is true for all positive integers .

Solution 2 (modular arithmetic)

Let us enumerate the remainders of and modulo :

We can see that both and have repeated remainders modulo for every three consecutive values of . The pattern is preserved due to properties of moduli arithmetic. Therefore, the sum is divisible by for any positive integer .

Problem 10 (25 points)

The number denotes the product . Let be a prime number. Prove the following equality in :

Solution

Let’s consider the numbers modulo . These numbers are all invertible modulo since is prime. We would like to pair them up so that their product is congruent to modulo . We can pair with for each in the set . However, we need to be careful to check if , which happens if , or , or . This equation has two solutions and . Therefore, we can pair all numbers except and . The product of all numbers in the set is congruent to modulo . Therefore, modulo .

The only case when the proof above does not work is when , and then . In this case, modulo .

The problem becomes significantly easier to solve if one starts by looking at a reasonable example. Let us take . Then . But , , . Therefore, in .