4

Find the smallest $n$ with $(113^{13})^n \equiv 113 \bmod 155$

My thoughts: Since the multiplicative ring $\mathbb{Z}_{155}$ has $155$ elements, then $a^{155}= 1$ for all $a \in \mathbb{Z}$
Hence $113^{155} \equiv 1 \bmod 155$ Then I noticed that $12 \cdot 13=155+1$ and hence $n=12$, but I don't know how to check this. Is this correct? Is there any algorithm to find $n$ in more complicated cases?

Arturo Magidin
  • 398,050
The Lion King
  • 794
  • Does $12$ work? working $\pmod 5$ we see $113\equiv 3\pmod 5$ and $13\equiv 1 \pmod 4$ so $113^{13}\equiv 3^1\equiv 3 \pmod 5$ and $3^{12}\equiv 1\pmod 5$. – lulu Jan 24 '23 at 17:17
  • 1
    More broadly, I suggest solving the problem $\pmod 5$ and $\pmod {31}$. Always easier to work with smaller numbers. – lulu Jan 24 '23 at 17:18
  • No $a^{155}\equiv 1\pmod {155}$ just take $a=115$ –  Jan 24 '23 at 18:10
  • So, for all $a\in\mathbb{Z}$ is wrong –  Jan 24 '23 at 18:13
  • 1
    You misapplied Lagrange's theorem. The entire ring is not a group. Rather the unit group of all elements coprime to $155$ has size $\phi(155) = \phi(5)\phi(31) = 4(30) = 120$, where $\phi = $ Euler totient. – Bill Dubuque Jan 25 '23 at 01:19
  • In general, the nonzero elements of a ring form a multiplicative monoid, but not necessarily a group. If it forms a group (every nonzero element is a unit) you have a field. – calc ll Jan 25 '23 at 06:38

1 Answers1

2

Since $(113,155)=1,$ we can divide out $113.$ Get $113^{13n-1}\equiv 1\pmod {155}.$

By Euler's theorem, $113^{\varphi (155)}\equiv 113^{120}\equiv 1\pmod {155}.$

So the order of $113\pmod {155}$ divides $120$. It's easy to check that that order is $60.$

So, $60\mid(13n-1)\implies n=37.$

(I found $13^{-1}\equiv 37\pmod {60}$ by some twiddling. You could also use the extended Euclidean algorithm.

calc ll
  • 8,427
  • I think you mean $n=37$. – J.G. Jan 24 '23 at 23:10
  • Is $120$ the smallest positive integer $m$ satisfying $113^m \equiv 1 \pmod{155}$? It may or may not be as far as I know, but either way it does need to be established IMO. 2. I don't think $120$ divides $(13 \cdot 27) -1$ as even $3$ does not divide $(13 \cdot 27)-1$.
    • – Mike Jan 24 '23 at 23:11
  • You're right. @J.G. – calc ll Jan 24 '23 at 23:29
  • Right @Mike. I also decided that it didn't need to be established. – calc ll Jan 24 '23 at 23:31
  • Error The inference in the third line assumes that $113$ has order $120,,$ mod $115$. The correct order is $60$. But - by luck - the answer is correct even though the argument is not, because $13^{-1}\bmod 60 = 37,$ too, and $,37 < 60,$ so it's the least inverse $!\bmod 60,$ (which fails if the order was a divisor of $120$ that's $< 37)\ \ $ – Bill Dubuque Jan 25 '23 at 00:54
  • Also, what do you mean by "the only other choice is $n = 1$"? The correct answer is $,n = 13^{-1}\bmod{k},,$ where $k =$ order of $ 113\pmod{155}.,$ Here $,k = 60.,$ In any case this question is a dupe of a FAQ so should not have been answered. It will likely be deleted, – Bill Dubuque Jan 25 '23 at 01:07
  • Thanks for the correction @BillDubuque. See my edit. – calc ll Jan 25 '23 at 05:54