3
$\begingroup$

If $N$ is the integer $2^43^35^27$ find the smallest positive integer $m$ such that $x^m \equiv 1 \mod N$ for all integers coprime to $N$.

I understand that I can do this for individual $N$ ($N= 2^4, 3^3, 5^2, 7$) and then take the LCM by Chinese Remainder Theorem. Using Fermat's Little Theorem doesn't give me the largest such $m$ for each choice of $N$. What's the relevant theorem/tool here?

EDIT (per suggestions): Applying the Euler phi-function gives us $\phi(2^4) = 8, \phi(3^3) = 3^2\times 2, \phi(5^2) = 5*4, \phi(7) = 6$.

Why are these the smallest such $m$?

$\endgroup$
  • $\begingroup$ Euler's theorem could work. $\endgroup$ – 伽罗瓦 Aug 19 '17 at 21:15
  • $\begingroup$ maybe Euler's theorem edit: of which Fermat's little theorem is a special case. $\endgroup$ – user451844 Aug 19 '17 at 21:15
  • 2
    $\begingroup$ This is known as Carmichael function. $\endgroup$ – Jyrki Lahtonen Aug 19 '17 at 21:21
  • $\begingroup$ When x is coprime to N, it can't hit any of the remainders not coprime to n. How many are coprime to N?, phi of N, by pigeonhole principle, it has to repeat by then. $\endgroup$ – user451844 Aug 19 '17 at 21:23
3
$\begingroup$

$\color{Green}{\text{Lemma}}$:

  • For every odd prime number $p$; and for every positive integer $\alpha$;
    the multiplicative group $\mathbb{Z}_{p^{\alpha}}^*$;
    is a cyclic group of order $\phi(p^{\alpha})= (p-1)p^{\alpha-1}$.
    In other words:

$$ \big( \mathbb{Z}_{p^{\alpha}}^* \ , \times \big) \equiv \big( \mathbb{Z}_{(p-1)p^{\alpha-1}} \ , + \big) . $$

  • For $\color{Red}{p=2}$; and for every positive integer $\color{Red}{3 \leq \alpha}$;
    the multiplicative group $\mathbb{Z}_{2^{\alpha}}^*$;
    is the direct sum of $\mathbb{Z}_2$ and a cyclic group of order $\color{Red}{\dfrac{1}{2}}\phi(2^{\alpha})= \color{Red}{2^{\alpha-2}}$.
    In other words:

$$ \big( \mathbb{Z}_{2^{\alpha}}^* \ , \times \big) \equiv \big( \mathbb{Z}_2 \oplus \mathbb{Z}_{\color{Red}{2^{\alpha-2}}} \ , + \big) . $$

  • The multiplicative group $\mathbb{Z}_{2^2}^*$; is a cyclic group of order $2$.
    The multiplicative group $\mathbb{Z}_{2}^*$; is the trivial group.


$\color{Teal}{\text{Remark}}$:

Let's define the function $\psi$ as follows:

  • For every odd prime number $p$; and for every positive integer $\alpha$;
    $ \psi(p^{\alpha}) = \phi(p^{\alpha}) = (p-1)p^{\alpha-1} . $

  • For $\color{Red}{p=2}$; and for every positive integer $\color{Red}{3 \leq \alpha}$;
    $ \psi(2^{\alpha}) = \color{Red}{\dfrac{1}{2}}\phi(2^{\alpha}) = \color{Red}{2^{\alpha-2}} . $

  • $\psi(4)=\phi(4)=2.$

  • $\psi(2)=\phi(2)=1.$

  • $\psi(1)=\phi(1)=1.$


  • If $n$ has the prime factorization $ n = \color{Red}{2^{\alpha_0}} p_1^{\alpha_1} p_2^{\alpha_2} ... p_k^{\alpha_k} $ ;
    with $\alpha_0 \in \mathbb{N}_0=\mathbb{N} \cup \{ 0 \} $ ; $\alpha_1 \in \mathbb{N}$ , $\alpha_1 \in \mathbb{N}$ , $...$ $\alpha_k \in \mathbb{N}$ ; then let's define: $ \psi(n) = \text{lcm} \Big( \psi(2^{\alpha_0}); \psi(p_1^{\alpha_1}), \psi(p_2^{\alpha_2}), ..., \psi(p_k^{\alpha_k}) \Big) $




One can easilly checks that :

$$\color{Teal}{\psi(n)} \color{Green} { \text{is the least integer} \ m \ \\ \text{such that} \ x^m \overset{n}{\equiv} 1 \ ; \\ \text{for all integers} \ x \ \text{coprime to} \ n \ }.$$


In your case the answer is:

$$ \psi(\color{Red}{2^4} . 3^3 . 5^2 . 7) = \text{lcm} \Big( \psi(\color{Red}{2^4}); \ \psi(3^3), \ \psi(5^2), \ \psi(7) \Big) = \\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{lcm} \Big( \color{Red}{2^2}; 2 \times 3^2, 4 \times 5, 6 \Big) = 2^2 \times 3^2 \times 5 = 180 . $$

$\endgroup$
  • $\begingroup$ The Euler totient of$16$ is $4$? Not $8$? $\endgroup$ – Oscar Lanzi Aug 21 '17 at 15:28
  • $\begingroup$ @Oscar Lanzi ; Yes you are right but $\psi(16)=\dfrac{1}{2}\phi(16)=\dfrac{1}{2}8=4$. $\endgroup$ – Jungle Boy Aug 21 '17 at 15:32

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.