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

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?

• it is 20 by the way – Saketh Malyala Jun 8 '19 at 5:22
• en.wikipedia.org/wiki/Multiplicative_order – Saketh Malyala Jun 8 '19 at 5:23
• Please fix the formatting of your question with Mathjax. – StephenG Jun 8 '19 at 5:25
• See here. $17\equiv1\pmod4$ so you only need to worry about the powers modulo $25$. $17\equiv2\pmod5$ so its order is a multiple of four given that $2$ generates $\Bbb{Z}_5^*$. Therefore the order is either $4$ or $20$, and you can eliminate the former. – Jyrki Lahtonen Jun 8 '19 at 5:39
• Possible duplicate of $x^{20}=1$ for all $x\in U(100)$ – Jyrki Lahtonen Jun 8 '19 at 5:39

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}

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}

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$$

• Nice one ! (+1) – Shaswata Jun 8 '19 at 7:33
• Why by seeing only 2400 being divisible by 100 ,one can say 4 MUST divide n?? Please reply ... – Riya Verma Sep 17 '19 at 4:12
• @Riya, $17^n\equiv1\pmod{100}\implies7^n\equiv1\pmod{10}$ right? – lab bhattacharjee Sep 17 '19 at 4:13

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}$$

$$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$$

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.

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'
$$\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}$$