1
$\begingroup$

I'll just upload a Brilliant page first. Check this out please.

enter image description here enter image description here enter image description here enter image description here enter image description here enter image description here enter image description here enter image description here enter image description here enter image description here

Now, what I don't understand are three parts.

  1. I get it, when they say it's important to have a multiplicative inverse there. You have to have a multiplicative inverse to return to the 1. But how does that guarantee some cycle would come back to where it started which is not 1? Like, if you start at 13 or whatever and keep multiplying a number, and how do you be sure about the cycle would come back to 13 just because the multiplying number has the inverse to the module?

  2. Again, they said that this whole process is related to the multiplicative inverse, and that's why it's true that the cycles that have numbers relatively prime to the module have same length each other. This is the most confusing one to me. Firstly, I don't even get why they furtively change the subject from "the number being multiplied is relatively prime to the module" to "the numbers in the cycles are relatively prime to the module". Furthermore how can you confidently say that multiplying the integers of one cycle by some fixed integer will give you a unique integer from the other cycle?

  3. They say all that that's all about being relatively prime to the module or not. But as you can see in the picture below, I think there's more to it than that. enter image description here Look, the red cycle has numbers that are not relatively prime to the module, 14, and it still has the same length and the same figure with the black one.

$\endgroup$
1
$\begingroup$

The integers which are coprime to $n$ form a group under multiplication modulo $n$. Denote this group by $G$.

Let $H$ be the group of powers of $a$ modulo $n$ for some $a$ coprime to $n$.

The multiplicative cycles in $G$ are the cosets of $H$ in $G$.

Let $g_1H$, $g_2H$ be two such cosets. These two cosets must contain the same number of elements because $f(x)=g_2g_1^{-1}x$ is a bijection from $g_1H$ to $g_2H$.


Your example in #3 can be generalized as follows.

Let $a$ be coprime to $n$, $q$ be a divisor of $n$ and $a$ be coprime to $q$. Then the cycle $a^k$ and the cycle $qa^k$ are of the same length; $f(x)=qx$ is a bijection because $qa^k$ will always be a multiple of $q$ modulo $n$ and so $f^{-1}(x)=x/q$ is well-defined.

$\endgroup$
2
  • $\begingroup$ Thanks, but I had no idea how should I interpret your answer. Why is $f(x)=g_2g_1^{-1}x$ a bijection? Futhermore, it doesn't seem to solve the #3. $\endgroup$
    – user800956
    Jul 8 '20 at 16:21
  • $\begingroup$ $f$ is a bijection because it has an inverse $f^{-1}=g_1g_2^{-1}$ $\endgroup$ Jul 8 '20 at 17:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.