Question

Show that if \(n\) is a positive integer, and \(a\) and \(b\) are integers relatively prime to \(n\) such that \(\left(\right.\) ord \(_{n} a\), ord \(\left._{n} b\right)=1\), then ord \(_{n}(a b)=\) ord \(_{n} a .\) ord \(_{n} b\).

Short answer

Question: Prove that if the orders of integers \(a\) and \(b\) modulo \(n\) are relatively prime, i.e., \((\text{ord}_n a, \text{ord}_n b) = 1\), then \(\text{ord}_n(ab) = \text{ord}_n a \cdot \text{ord}_n b\). Solution: To prove this, we followed two steps. First, we established that \((a^k b^k) \mod n \equiv 1\) when \(k=\text{ord}_n a \cdot \text{ord}_n b\). Then, we proved that there is no positive integer smaller than \(k\) for which \((ab)^l \equiv 1 \pmod{n}\). Thus, we have shown that \(\text{ord}_n(ab) = \text{ord}_n a \cdot \text{ord}_n b\).

Step-by-step solution

Establish that \((a^k b^k) \mod n \equiv 1\)

First, let's establish that \((a^k b^k) \mod n \equiv 1\) when \(k=\text{ord}_n a \cdot \text{ord}_n b\). Let \(\text{ord}_n a = m\) and \(\text{ord}_n b = q\). Then we have $$a^m \equiv 1 \pmod{n}, \quad b^q \equiv 1 \pmod{n}.$$ Now, consider \(k = mq\). If we raise both \(a\) and \(b\) to the power of \(k\), we get: $$a^k \equiv a^{mq} \equiv (a^m)^q \equiv 1^q \equiv 1 \pmod{n},$$ and $$b^k \equiv b^{mq} \equiv (b^q)^m \equiv 1^m \equiv 1 \pmod{n}.$$ So, we have shown that \(a^k \equiv 1 \pmod{n}\) and \(b^k \equiv 1 \pmod{n}\) when \(k = mq\). Now we need to show that \((ab)^k \equiv 1 \pmod{n}\). Since \(a^k \equiv 1 \pmod{n}\) and \(b^k \equiv 1 \pmod{n}\), we can multiply both sides of each congruence to get: $$a^k b^k \equiv 1 \cdot 1 \pmod{n}.$$ Thus, we have \((ab)^k \equiv 1 \pmod{n}\).

Prove that there is no positive integer smaller than \(k\) for which \((ab)^l \equiv 1 \pmod{n}\)

Now, let's assume to the contrary that there exists \(l < k = mq\) such that \((ab)^l \equiv 1 \pmod{n}\). If this is the case, then $$a^l b^l \equiv 1 \pmod{n}.$$ If we multiply both sides by \(a^{-l}\) and apply the properties of modular arithmetic, we get $$b^l \equiv a^{-l} \pmod{n}.$$ By Euler's theorem, we know that \(a^{\varphi(n)} \equiv 1 \pmod{n}\), since \(a\) and \(n\) are relatively prime. So, let's multiply both sides of the congruence \(b^l \equiv a^{-l} \pmod{n}\) by \((a^{\varphi(n)})^l\): $$b^l (a^{\varphi(n)})^l \equiv a^{-l}(a^{\varphi(n)})^l \pmod{n}.$$ Since \(b\) and \(n\) are relatively prime as well, we can apply Euler's theorem to \(b\) as well: $$a^{l\varphi(n) - l} \equiv b^{l\varphi(n)} \equiv 1 \pmod{n}.$$ Now, \(a^{l\varphi(n) - l} \equiv 1 \pmod{n}\) implies that \(m \mid l\varphi(n) - l\). Similarly, as \(b^{l\varphi(n) - l} \equiv 1 \pmod{n}\), \(q \mid l\varphi(n) - l\). As \((m,q)=1\), we have \(mq \mid l\varphi(n) - l\). However, we assumed that \(l < k = mq\), which leads us to a contradiction. Thus, there is no positive integer smaller than \(k = \text{ord}_n a \cdot \text{ord}_n b\) for which \((ab)^l \equiv 1 \pmod{n}\). Therefore, we have shown that \(\text{ord}_n(ab) = \text{ord}_n a \cdot \text{ord}_n b\).

Key concepts

Order of an Integer

The concept of "order of an integer" in modular arithmetic tells us about the smallest positive integer, let's call it \( k \), such that raising an integer \( a \) to the power of \( k \) results in 1 modulo \( n \). In mathematical terms, this can be expressed as \( a^k \equiv 1 \pmod{n} \).

• The order of \( a \) modulo \( n \), often written as \( \text{ord}_n a \), is a foundational concept that helps to understand how numbers behave within modular arithmetic systems.
• If an integer \( a \) and the modulus \( n \) are relatively prime, meaning they share no common divisors other than 1, then the order exists and is well-defined.

To find this "order", you essentially check various powers of \( a \) modulo \( n \) until you arrive at \( 1 \). For instance, if \( a \equiv 2 \pmod{5} \), you check powers of 2 (like \( 2^1, 2^2, \) etc.) until you find one that equals 1 modulo 5. This foundational concept is crucial for solving many problems in number theory as it uncovers a cyclic nature in modular systems.

Modular Arithmetic

Modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" upon reaching a certain value, known as the modulus. It's like the way hours wrap around after 24 in a clock.

• In mathematical notation, two numbers \( a \) and \( b \) are said to be congruent modulo \( n \) if they give the same remainder when divided by \( n \), written as \( a \equiv b \pmod{n} \).
• This concept is not just theoretical. It's used in real-world applications like cryptography, computer science, and coding systems.

The power of modular arithmetic lies in its ability to simplify complex calculations by focusing only on remainders. When dealing with equations within modular arithmetic, operations like addition, subtraction, and multiplication behave similarly to regular arithmetic but with an extra step of taking results modulo \( n \). These properties make it particularly useful for solving equations involving cyclic systems.

Relatively Prime Integers

When two integers are said to be relatively prime, it means they have no shared positive divisors other than 1. This is a special relationship in number theory that indicates a unique compatibility between the numbers involved.

• If \( a \) and \( n \) are relatively prime, they satisfy the condition \( \gcd(a, n) = 1 \), where \( \gcd \) stands for "greatest common divisor".
• This uniqueness is essential in modular arithmetic, especially in operations involving inverses and solving certain types of congruences like those posed by Euler's theorem.

For example, if \( a = 5 \) and \( n = 12 \), since their greatest common divisor is 1, they are relatively prime. This relationship allows for simplifications in problems and lays the groundwork for many theorems and proofs involving modular systems. Recognizing when numbers are relatively prime is a crucial skill in number theory and forms the bedrock for many higher-level concepts.