Question

Show that if \(\bar{a}\) is an inverse of \(a\) modulo \(n\), then ord \(_{n} a=\) ord \(_{n} \bar{a}\).

Short answer

" Answer: Yes, if \(\bar{a}\) is an inverse of \(a\) modulo \(n\), then the order of \(a\) modulo \(n\) is equal to the order of \(\bar{a}\) modulo \(n\).

Step-by-step solution

Recall Definitions

The order of an element \(a\) modulo \(n\), denoted by ord\(_{n}a\), is the smallest positive integer \(k\) such that \(a^k \equiv 1 \pmod{n}\). The inverse of an element \(a\) modulo \(n\), denoted by \(\bar{a}\), is another element such that \(a\bar{a}\equiv 1 \pmod{n}\).

Prove ord\(_{n}a\) Divides ord\(_{n}\bar{a}\)

Assume that ord\(_{n}a = k\). This means that \(a^k \equiv 1 \pmod{n}\). Now, we want to show that ord\(_{n}a\) divides ord\(_{n}\bar{a}\). Let's assume that ord\(_{n}\bar{a} = l\). This means that \(\bar{a}^l \equiv 1 \pmod{n}\). We will raise both sides of \(a\bar{a}\equiv 1 \pmod{n}\) to the power of \(k\): \((a\bar{a})^k \equiv 1^k \pmod{n} \Rightarrow a^k\bar{a}^k \equiv 1 \pmod{n}\) Since we know that \(a^k \equiv 1 \pmod{n}\), we can substitute this in the previous equation: \(1 \cdot \bar{a}^k \equiv 1 \pmod{n} \Rightarrow \bar{a}^k \equiv 1 \pmod{n}\) This means that \(k\) divides ord\(_{n}\bar{a}\) or, in other words, ord\(_{n}a| \text{ ord}_{n}\bar{a}\).

Prove ord\(_{n}\bar{a}\) Divides ord\(_{n}a\)

Similarly, we will raise both sides of \(a\bar{a}\equiv 1 \pmod{n}\) to the power of \(l\): \((a\bar{a})^l \equiv 1^l \pmod{n} \Rightarrow a^l\bar{a}^l \equiv 1 \pmod{n}\) Since we know that \(\bar{a}^l \equiv 1 \pmod{n}\), we can substitute this in the previous equation: \(a^l \cdot 1 \equiv 1 \pmod{n} \Rightarrow a^l \equiv 1 \pmod{n}\) This means that \(l\) divides ord\(_{n}a\) or, in other words, ord\(_{n}\bar{a}| \text{ ord}_{n}a\).

Conclude the Proof

From Step 2, we have shown that ord\(_{n}a\) divides ord\(_{n}\bar{a}\), and from Step 3, we have shown that ord\(_{n}\bar{a}\) divides ord\(_{n}a\). Therefore, we can conclude that ord\(_{n}a = \text{ ord}_{n}\bar{a}\).

Key concepts

Order of an Element

The "order of an element" in modular arithmetic is a fundamental concept. Let's dive into what it actually means. Consider a number "\(a\)" in the context of modulo "\(n\)." The order of this element, denoted as \( \text{ord}_n a \), is the smallest positive integer "\(k\)" for which the congruence \( a^k \equiv 1 \pmod{n} \) holds true.

Intuitively, you are cycling through powers of \(a\) until you end up where you started, back at 1, but under modulo arithmetic conditions. Think of it like a repeating pattern!

• Essentially: Find "\(k\)" such that \(a^k - 1\) is divisible by "\(n\)".
• Example: For \(a = 2\) and \(n = 7\), \((2^3 \equiv 1 \pmod{7})\), thus \(\text{ord}_7 2 = 3\).

Understanding the order of an element is crucial, as it helps in exploring cyclic properties, and it's fundamental in proofs within modular arithmetic.

Modular Inverse

Understanding a "modular inverse" is key to solving many modular arithmetic problems. When we talk about the modular inverse of an integer \(a\) under a modulus \(n\), we are looking for another integer, denoted as \(\bar{a}\), such that \(a\bar{a} \equiv 1 \pmod{n}\).

It's a bit like finding the number that, when multiplied by \(a\), results in 1 under a world defined by \(n\). This is only possible if \(a\) and \(n\) are coprime (meaning their greatest common divisor is 1).

• Key Insight: Multiply \(a\) by \(\bar{a}\) to cycle back to 1; this process ensures reversibility in modular arithmetic.
• Example: In modulo 7, the modular inverse of \(3\) is \(5\), because \(3 \times 5 \equiv 1 \pmod{7}\).

Finding these inverses is critical in cryptography and solving congruences, serving as the backbone of various algorithms.

Congruence Relation

A "congruence relation" is an equivalence relation in modular arithmetic. It shows that two numbers have the same remainder when divided by a given modulus \(n\). If two numbers \(a\) and \(b\) are congruent modulo \(n\), then we write \(a \equiv b \pmod{n}\). This means \(n\) divides the difference \(a - b\).

This concept allows us to group numbers into "congruence classes," where numbers in the same class share the characteristic of having the same remainder when divided by \(n\).

• Illustration: For \(n = 5\), \(8 \equiv 3 \pmod{5}\), because both leave a remainder of 3 when divided by 5.
• Congruence relations are used to simplify calculations and solve equations within the constraints of a modulus.

Understanding congruence helps in analyzing and solving various number theory problems. It's an essential idea for efficiently managing calculations and proofs in modular arithmetic.