characterization of relative primality of two numbers
2025 Aug 20
See all posts
characterization of relative primality of two numbers
I was 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 conclusion \[\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 (and general) 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 was 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 conclusion \[\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 (and general) 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\]