characterization of relative primality of two numbers
2025 Aug 20
See all posts
characterization of relative primality of two numbers
I working through cyclic groups
exercises in Pinter's book. There was one question in the "Elementary
Properties of Cyclic Subgroups of Groups":
Let \[ ord(a) = n \] and \(b = a^k\). Then \(<a> = <b>\) iff n and k are
relatively prime.
To prove this we need to establish results both sides:
- \(\langle a \rangle = \langle b \rangle
\Rightarrow\) \(n\) and \(k\) are relatively prime
- \(n\) and \(k\) are relatively prime \(\Rightarrow \langle a \rangle = \langle b
\rangle\)
In solving the first half of this, I came across the result \[\exists p \in \mathbb{Z}, \, 1 \leq p \leq n
\text{ such that } pk-1 \equiv 0 \pmod{n} \] or \[ pk = 1 \pmod{n} \]
After some thinking I realized that this means \(k\) and \(n\) are relatively prime. Turns out this is
exactly how primality is characterized via Bezout's
Identity (modular arithmetic form):
\(a\) and \(n\) are relatively prime iff \(a\) has multiplicative inverse modulo \(n\) i.e. there exists a \(x\) such that \[
ax \equiv 1 \pmod{n} \]
Another and perhaps more common representation is:
for \(a,b \in \mathbb{Z}\) \(\exists x,y \in \mathbb{Z}\) \[ ax+by = gcd(a,b) \]
if relatively prime, this turns out to be \[ ax+by = 1\].
characterization of relative primality of two numbers
2025 Aug 20 See all postsI working through cyclic groups exercises in Pinter's book. There was one question in the "Elementary Properties of Cyclic Subgroups of Groups":
Let \[ ord(a) = n \] and \(b = a^k\). Then \(<a> = <b>\) iff n and k are relatively prime.
To prove this we need to establish results both sides:
In solving the first half of this, I came across the result \[\exists p \in \mathbb{Z}, \, 1 \leq p \leq n \text{ such that } pk-1 \equiv 0 \pmod{n} \] or \[ pk = 1 \pmod{n} \]
After some thinking I realized that this means \(k\) and \(n\) are relatively prime. Turns out this is exactly how primality is characterized via Bezout's Identity (modular arithmetic form):
\(a\) and \(n\) are relatively prime iff \(a\) has multiplicative inverse modulo \(n\) i.e. there exists a \(x\) such that \[ ax \equiv 1 \pmod{n} \]
Another and perhaps more common representation is:
for \(a,b \in \mathbb{Z}\) \(\exists x,y \in \mathbb{Z}\) \[ ax+by = gcd(a,b) \]
if relatively prime, this turns out to be \[ ax+by = 1\].