Number Theory and ...

Number theory¶

Task 1¶

Check the following congruences:

1. \(12 \equiv 2 \pmod{5}\)
2. \(12 \equiv 3 \pmod{10}\)
3. \(21 \equiv 1 \pmod{5}\)
4. \(23 \equiv 3 \pmod{4}\)

Task 2¶

Probe that if \(a \equiv b \pmod{n}\) and \(c \equiv d \pmod{n}\), then:

1. \(a+c \equiv b+d \pmod{n}\)
2. \(a-c \equiv b-d \pmod{n}\)
3. \(ac \equiv bd \pmod{n}\)
4. \(a^k \equiv b^k \pmod{n}\) for all \(k \in \mathbb{N}\)

Task 3¶

Compute the following greatest common divisors (use the Euclidean algorithm):

1. \(\gcd(12, 75)\)
2. \(\gcd(12, 68)\)
3. \(\gcd(72, 55)\)
4. \(\gcd(45, 42)\)

Task 4¶

Compute the following least common multiples:

1. \(\text{lcm}(12, 10)\)
2. \(\text{lcm}(12, 14)\)
3. \(\text{lcm}(72, 25)\)
4. \(\text{lcm}(45, 60)\)

Task 5¶

Solve congruences of the form \(ax \equiv b \pmod{m}\):

1. \(2x \equiv 3 \pmod{5}\)
2. \(3x \equiv 4 \pmod{7}\)
3. \(4x \equiv 5 \pmod{6}\)
4. \(5x \equiv 6 \pmod{8}\)
5. \(6x \equiv 7 \pmod{9}\)

Induction¶

Task 1¶

Prove the following statements by induction:

1. \(1 + 2 + \dots + n = \frac{n(n+1)}{2}\) for all \(n \in \mathbb{N}\).

Task 2¶

Prove the following statements by induction:

1. \(1+3+5+\dots+(2n-1)=n^2\) for all \(n \in \mathbb{N}\).

Task 3¶

Prove the following statements by induction:

1. \(1^2 + 2^2 + \dots + n^2 = \frac{n(n+1)(2n+1)}{6}\) for all \(n \in \mathbb{N}\).

Task 4¶

Prove the following statements by induction:

Task 5¶

Task 6¶

Prove the following statements by induction:

1. \(k! \geq 2^k\) for all \(k\geq 4\)
2. \(37^{500}-37^4\) is divisible by 10.
3. For \(n\geq0\)