1

I was given the following problem:

Find the smallest positive integer $m$ such that $$(49^{13})^m \equiv 49 \pmod{155}.$$

My approach:

We know that $\varphi(155) = 120$ and $\gcd(49,155) = 1$. Thus Euler's Theorem tells us that $$49^{120} \equiv 1 \pmod{155},$$ so we can conclude that $$49^{120k} \equiv 1 \pmod{155}$$ holds for every $k \in \mathbb{N}$. Now I found $k = 4$ to be the smallest integer such that $m := \frac{120k + 1}{13} = 37 \in \mathbb{N}$ holds. This $m$ now fulfills the equation $$\begin{aligned} 49^{13m-1} &\equiv 1 \pmod{155} \\ \iff (49^{13})^m &\equiv 49 \pmod{155}.\end{aligned}$$ Unfortunately this isn't the smallest positive integer $m$. Any suggestions for a better approach?

(By Brute Force I found the solution to be $m = 7$ if this helps.)

Dedekind
  • 183

1 Answers1

1

First find the order of $49 \mod 155$. It is a divisor of $\varphi(155) = 120$. By trying (using repeated squaring) we find $49^{30} \equiv 1$ but $49^{15} \equiv 94 \not\equiv 1$, $49^{10} \equiv 36\not\equiv 1$ and $49^{6} \equiv 16 \not\equiv 1$, so the order is $30$. (See EDIT for easier method.) Any exponent of $49$ that yields $1$ must be a multiple of this order. Hence for some $n\in \mathbb{Z}$

$$13m-1 = 30n$$

So we must solve this linear Diophantine equation and find the solution with the smallest positive $m$. Standard method gives the solution

$$(m,n) = (30c+7, 13c+3), \space \space c\in\mathbb{Z}$$

where we can alredy see the wanted solution $m=7$.

EDIT Since $155 = 5 \cdot 31$ and $\gcd(5, 31)=1$, you can also find the order of $49$ by finding its order $\mod 5$ and $\mod 31$ and taking their least common multiple. The first one is trivial, since $49 \equiv -1 \mod 5$, so the order is $2$. The calculation $\mod 31$ is also quite easy, since $\varphi(31) = 30$ which has divisors $1, 2, 3, 5, 6, 10, 15, 30$. Now it's the matter of similar checking as originally but the modulus and the exponents are smaller. We find the order $\mod 31$ is $15$.

ploosu2
  • 8,707