4
$\begingroup$

First for it's importance in the field of abstract algebra:

  • This function returns the cardinality (order) of the group $U(n)$ closed under modular multiplication.

  • This function also returns the upper bound for the order of an arbitrary element in the $U(n)$.

And after that it's computational importance in modular arithmetic:

  • Since residue exponention is not well-defined, reducing the exponent modulo $\varphi(m)$ is our only way out for simplyfing modular exponents due to the Euler-Totient theorem.

  • With the same way above, if exponent of the element is relatively prime with the $\varphi(m)$, we can compute modular inverse of the exponent and with the help of it we can calculate modular roots. It is essential to RSA.

Are my points true? What i can add to this list?

$\endgroup$
  • 4
    $\begingroup$ For the second point, see Carmichael's function, which gives the best upper bound for multiplicative orders modulo $n$. $\endgroup$ – lhf Jul 5 at 14:06
  • $\begingroup$ I'd say the core of modular arithmetic is the decomposition of the groups $\Bbb{Z}_n,\Bbb{Z}_n^\times$ and the ring $\Bbb{Z}_n$ in term of prime powers $p^k | n$ and $\varphi(n)$ encodes one of the main parameters of those things $\endgroup$ – reuns Jul 5 at 22:03
  • $\begingroup$ This question overlaps math.stackexchange.com/q/2816053. $\endgroup$ – Steven Clark Jul 6 at 17:41
6
$\begingroup$

A few things:

  • You reduce many term polynomials, to just a few terms mod any value. (see here as applied to an integer, a less general form of polynomial).

  • It shreds power towers down to size, with repeated use.

  • It allows us to work in smaller numbers, rather than potentially trillion digit numbers.

  • It allows us to pigeonhole principle coprime variable sets.

  • You can generalize it to products of coprime arithmetic progressions. The product of the first 4 numbers in arithmetic progression 10k+9 have a product that is 1 mod 10 for example (193,401 for those wondering).

  • Can be used to limit long division in finding the reptend length of fractions with coprime denominator in a given base.

  • Cryptography ( forgot this)

    • etc.
$\endgroup$
3
$\begingroup$

Another reason from abstract algebra:

If $n$ is a positive integer then every group of order $n$ is cyclic if and only if $\gcd(n,\varphi(n))=1$.

You can read about the history and proof of this result here.

$\endgroup$

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.