0
$\begingroup$

Find the minimal $t$, $t\in\mathbb{N}$ such that $113^t \equiv 1\bmod(455)$.

I received this problem in introductory number theory so I have tried to use the basic properties of modular congruences and other division-based properties. So I have tried identifying the following, Using the property that $a\equiv b\bmod(n)$ and $m\mid n$ then $a\equiv b\bmod(m)$ and then, \begin{align} 113^t \equiv1\bmod(5) \\ 113^t \equiv1\bmod(7) \\ 113^t \equiv1\bmod(13) \\ \end{align} Then we get a system of linear congruences and then maybe if we let $113^t$ be $x$ then we can get $x$ and find a minimal $t$ satisfying that $x$. But does not seem to really work. Anyway, you could use Eulers theorem and the Eulers totient function and get $t=288$ which I don't know if is correct since I think $288$ is actually the maximal maybe(not sure)? But I want to solve this with more elementary methods without such concepts.

$\endgroup$
2
  • 1
    $\begingroup$ Actually, $113^{12}\equiv 1 \bmod 455$, see this duplicate, or many others. $\endgroup$ Oct 26, 2023 at 11:47
  • 1
    $\begingroup$ Note that when you are working modulo $5$, $113$ is the same as $3$; modulo $7$, $113=1$, and modulo $13$, $113=9=-4$. $\endgroup$ Oct 26, 2023 at 11:50

1 Answer 1

0
$\begingroup$

If $113^{288}\equiv1\pmod{455}$ then $113^{144}\equiv \pm 1\pmod{455}$. You can verify that $113^{144}\equiv 1\pmod{455}$ so $113^{12^2}\equiv 1\pmod{455}$ and $113^{12}\equiv 1\pmod{455}$. Since $113^{6}\equiv 274\pmod{455}$. You find now that the minimum exponent is $12$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .