Let's solve questions 4 to 7 step by step.

Question 4:

If $n, a,$ and $b$ are positive integers for which:

• $n$ is odd
• $a \equiv b \mod{\phi(n)}$

then $2^a \equiv 2^b \mod{n}$

This statement is True. It is a direct application of Euler's theorem which states that if $a \equiv b \mod{\phi(n)}$, then $x^a \equiv x^b \mod{n}$ for any integer $x$ that is coprime with $n$.

Question 5:

Given $S = \{a, 2a, 3a, \ldots, 69a, 70a\}$ with $a = 3$. Check all that apply.

Let's examine each statement:

• $3^{70} \equiv 1 \mod{71}$ Using Fermat's Little Theorem: $a^{p-1} \equiv 1 \mod{p}$ for any integer $a$ and a prime $p$, we get: $3^{70} \equiv 1 \mod{71}$ This statement is True.

• $a \cdot (2a) \cdot (3a) \cdots (69a)(70a) \equiv 70! \mod{71}$ We need to see if the product $a \cdot (2a) \cdots (70a)$ is congruent to $70! \mod{71}$. Simplifying this, we note that: $(3 \cdot 2 \cdot 3 \cdot \ldots \cdot 3 \cdot 70) \equiv 70! \mod{71}$ $3^{70} \cdot 70!$ Since $3^{70} \equiv 1 \mod{71}$, we have: $1 \cdot 70! \equiv 70! \mod{71}$ This statement is True.

• $S$ is a complete residue system $\mod{71}$ A complete residue system modulo 71 would contain every integer from 0 to 70 exactly once. Since $S$ is $3, 6, 9, \ldots, 210$, it will cycle through all residues because $3$ and $71$ are coprime, thus covering every residue exactly once. This statement is True.

Question 6:

If $p$ is an odd prime and $a$ is a positive integer for which $a \equiv 0 \mod{p}$, then $2^a \equiv 1 \mod{p}$.

This statement is True. Since $a \equiv 0 \mod{p}$, $a = kp$ for some integer $k$. Therefore: $2^a = 2^{kp} = (2^p)^k$ By Fermat's Little Theorem, $2^p \equiv 2 \mod{p}$ and $2^{p-1} \equiv 1 \mod{p}$. Therefore, $2^{kp} \equiv 1 \mod{p}$.

Question 7:

If $p$ and $q$ are odd primes, then $2^{pq-1} \equiv 1 \mod{pq}$.

This statement is True. It follows from Euler's theorem. For $n = pq$, we use $\phi(pq) = (p-1)(q-1)$. Euler's theorem tells us: $2^{\phi(pq)} \equiv 1 \mod{pq}$ Since $\phi(pq) = (p-1)(q-1)$ and $pq-1$ is one less than $pq$, it satisfies the theorem.

Would you like more details on any of these questions or have any further questions? Here are five more questions you might be interested in:

1. How can Euler's theorem be applied to cryptography?
2. What is Fermat's Little Theorem and how is it used?
3. How can we determine if a set forms a complete residue system?
4. What are the properties of modular arithmetic?
5. Can you provide examples of calculating modular exponentiation?

Tip:

Understanding the principles of modular arithmetic and number theory can greatly simplify solving problems involving congruences and the Euler's totient function.