It can then be decoded as PowerMod[c, e, n] , where e = PowerMod[d, -1, EulerPhi[n]] . But to find EulerPhi[n] (see page 1093 ) is equivalent in difficulty to finding the factors of n .

Other integer functions IntegerExponent[n, k] gives nested behavior as for decimation systems on page 909 , while MultiplicativeOrder[k, n] and EulerPhi[n] yield more complicated behavior, as shown on pages 257 and 1093 .

Every cycle corresponds in effect to a distinct necklace with n beads; with k colors the total number of these is Apply[Plus, (EulerPhi[n/#] k # &)[Divisors[n]]]/n The number of cycles of length exactly m is s[m, k]/m , where s[m, k] is defined on page 950 .

The smallest such t is given by MultiplicativeOrder[k, n] , which always divides EulerPhi[n] (see page 1093 ), and has a value between Log[k, n] and n - 1 , with the upper limit being attained only if n is prime.

Given p = Array[Prime, Length[list], PrimePi[Max[list]] + 1] or any list of integers that are all relatively prime and above Max[list] (the integers in list are assumed positive) CRT[list_, p_] := With[{m = Apply[Times, p]}, Mod[Apply[Plus, MapThread[#1 (m/#2)^EulerPhi[#2] &, {list, p}]], m]] yields a number x such that Mod[x, p]  list .

On row n the number of white squares encountered before reaching the leading diagonal is EulerPhi[n] .

For a register of size n the maximal period of 2 n -1 is obtained whenever x n + Apply[Plus, x taps - 1 ] is one of the EulerPhi[2 n - 1]/n primitive polynomials that appear in Factor[Cyclotomic[2 n - 1, x], Modulus  2] .