How can i get the least $n $ such that $17^n \equiv 1 \mod(100$)?

Question

When I solve the problem:
$17^{2018}\equiv r \pmod{100} $

used Euler theorem since $\gcd (17,100)=1$ and so

$\phi(100)=40$ and so

$17^{40}\equiv 1 \pmod{100}$

But i also found that: $17^{20}\equiv 1 \pmod{100}$

How can i get the least n such that $17^{n}=1\pmod{100} $?

Is there any theorm or generalization to this problem?

Thanks for your help

Answer 1

Euler's phi function, $\varphi(n)$, is a multiplicative function for which, if $a$ and $N$ are relatively prime, then $a^{\varphi(N)} \equiv 1 \pmod N$. In particular

$$\varphi(100) = \varphi(4)\varphi(25) = (4-2)(25-5)=40$$

So $17^{40} \equiv 1 \pmod{100}$. The smallest $n$ such that $17^n \equiv 1 \pmod{100}$ must therefore be a divisor of $40$.

The divisors of $40$ are $$1, 2, 4, 5, 8, 10, 20, 40$$

\begin{align} 17^1 &\equiv 17 \pmod{100} \\ 17^2 &\equiv 17\times17 \equiv 89 \pmod{100} \\ 17^4 &\equiv 89\times 89 \equiv 21 \pmod{100} \\ 17^5 &\equiv 17\times 21 \equiv 57 \pmod{100} \\ 17^8 &\equiv 21\times 21 \equiv 41 \pmod{100} \\ 17^{10} &\equiv 57\times 57 \equiv 49 \pmod{100} \\ 17^{20} &\equiv 49\times 49 \equiv 1 \pmod{100} \end{align}

Added 6/8/2019

In response to the comment of @labbhattacharjee, $\lambda(n)$, the Carmichael function of n, is defined by

For any power of a prime number, $n = p^\alpha$,

$$\lambda(n) = \begin{cases} \frac 12\varphi(n) & \text{If n is a power of $2$ that is $\ge 8$ }\\ \varphi(n) & \text{Otherwise} \end{cases}$$

For any prouduct of powers of unique prime numbers, $n=p_1^{\alpha_1} p_2^{\alpha_2} \dots p_k^{\alpha_k}$,

$$\lambda(n) = \operatorname{LCM} \{\lambda(p_1^{\alpha_1}), \lambda(p_2^{\alpha_2}), \dots, \lambda(p_k^{\alpha_k})\}$$

So

\begin{align} \lambda(100) &= \lambda(2^2 \cdot 5^2) \\ &= \operatorname{LCM}\{\lambda(2^2),\lambda(5^2)\} \\ &= \operatorname{LCM}\{\varphi(2^2),\varphi(5^2)\} \\ &= \operatorname{LCM}\{2,20 \} \\ &= 20 \end{align}

Answer 2

Use the binomial theorem to expand $$(10+7)^n$$

The following facts will be useful:

$$k \geq 2 \, \, \, \, \, \, \implies \, \, \, \, \, \, 10^k\equiv 0 \pmod{100}$$

$$7^4 \equiv 1 \pmod{100}$$

Answer 3

$$17^n\equiv (10+7)^n\equiv 7^n+n\cdot 7^{n-1}\cdot 10 \mod 100 $$

Coincidentally,

$$7^4 \equiv 1 \mod 100$$ $$\rightarrow 7^{-1}\equiv 7^3 \equiv 43 \mod 100$$

So we need to find the smallest $n$ such that,

$$7^n+n\cdot 7^{n-1}\cdot 10 = 7^n+n\cdot 7^{n}\cdot 43\cdot10\equiv 7^n(1+30\cdot n)\equiv 1\mod 100$$

$$7^{-n}\equiv 30n+1 \mod 100$$

However $7^n$ has only 4 possibilities -> ($7,49,43,1$). Only one of these can be of the form $30n+1$.

$$30n+1 \equiv 1 \mod 100$$

Implying that $10|n$

Also, $7^4\equiv 1 \mod 100$ implying that $4|n$

The smallest $n$ satisfying these conditions $n=20$

Answer 4

As $7^1\equiv7,\cdots,7^4\equiv1\pmod{10}$

$4$ must divide $n$

Let $n=4m$

$17^n=(290-1)^{2m}$

$=(1-290)^{2m}\equiv1-\binom{2m}1290\pmod{100}$

So,$100$ must divide $290\cdot2m$

Answer 5

Euler's theorem says that if $\gcd(a,n)=1$ then $a^{\phi(n)} \equiv 1 \pmod n$ but Euler's theorem does not say $\phi(n)$ is the smallest such number.[1]

But we can easily verify the smallest such power (called the order of $a$) will have to be a factor of $\phi(n)$ [2]

So test $17^k$ where $k|40$.

The powers twos are easy to calculate through repeated squaring.

$17^2 \equiv 89\pmod {100}$ and $17^4 \equiv 89^2\equiv (-11)^2 \equiv 21 \pmod {100}$ and $17^8\equiv 21^2 \equiv 41\pmod {101}$.

The multiples of $5$ are harder but ... well, check this out.

$17^{20} \equiv 21^5 \equiv (20+1)^5 \equiv 20^5 + 5*20^4 + 10*20^3 + 10*20^2 + 5*20 + 1\equiv 0+0+0+0+100 + 1 \equiv 1 \pmod {100}$.

Similarly $17^{10} \equiv (-11)^5 \equiv -(11)^5 \equiv -(10^5 + 5*10^4 + 10*10^3 + 10*10^2 + 5*10 + 1) \equiv -51 \equiv 49\pmod {101}$

Which means the smallest such power is $20$[3]

====

[1] Obviously if $a \equiv b^{k}$ and $k|\phi(n)$ then $a^{\frac {\phi(n)}k} = b^{\phi(n)}\equiv 1 \pmod n$ so this simply can't be true

Taking this to extreme: Obviously $\gcd(1,n) =$ and $1^1 \equiv 1 \pmod n$.

[2] If the order of $a$ is $k < \phi(n)$ and $k\not \mid \phi(n)$ then $\phi(n) = b*k + r$ for some $b$ and $0< r < k$.

So $1\equiv a^{\phi(n)}\equiv (a^{k})^ba^r \equiv 1^ba^r\equiv a^r\pmod n$. But we said $k$ was the least such power so that is a contradiction.

So the order of $a$ must divide $\phi(n)$.

[3]Any factor of $40$ that is less than $20$ is either a power of two (which we've ruled out) or a multiple of $5$. any smaller multiple of $5$ divides $10$. If $17$ to such a smaller power were equivalent to $1$ then $17^{10}$ would also be and it isn't.

Answer 6

We have that

$\tag 1 \text{<}[11]\text{>} = \{[01],[11],[21],[31],[41],[51],[61],[71],[81],[91]\}$

where $\text{<}[11]\text{>}$ is the multiplicative group generated by $[11]$ in $(\mathbb{Z}/{100}\mathbb{Z})^\times$.

Observe via a mental calculation that $17^4 \in \text{<}[11]\text{>}$ with $4$ the smallest exponent 'getting us there'
(c.f. lab bhattacharjee's answer).

Calculating we find that

$\tag 2 17^4 \equiv 21 \pmod{100}$

The order of $[21]$ in the cyclic group $\text{<}[11]\text{>}$ is equal to $5$.

So the cyclic group generated by $[17]$ has $4 \times 5$ elements; i.e. $20$ is the smallest positive integer such that

$\quad 17^{20} \equiv 1 \pmod{100}$