2
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ it is 20 by the way $\endgroup$ – Saketh Malyala Jun 8 '19 at 5:22
  • $\begingroup$ en.wikipedia.org/wiki/Multiplicative_order $\endgroup$ – Saketh Malyala Jun 8 '19 at 5:23
  • $\begingroup$ Please fix the formatting of your question with Mathjax. $\endgroup$ – StephenG Jun 8 '19 at 5:25
  • 1
    $\begingroup$ 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. $\endgroup$ – Jyrki Lahtonen Jun 8 '19 at 5:39
  • 3
    $\begingroup$ Possible duplicate of $x^{20}=1$ for all $x\in U(100)$ $\endgroup$ – Jyrki Lahtonen Jun 8 '19 at 5:39
0
$\begingroup$

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}

$\endgroup$
1
3
$\begingroup$

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$

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

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

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