0
$\begingroup$

I have to find a number x such that x is the smallest natural number that satisfies this equation:

$24x (\mod 59) = 2(\mod59)$.

Using Fermat's little theorem and Euler's primes function, given that 59 is a prime, I determined that

$24^{\phi 59} (\mod 59) =1 (\mod 59)$

$24^{58} (\mod 59) =1 (\mod 59)$

$2*24^{58} (\mod 59) =2 (\mod 59)$

$2* 24 * 24^{57} (\mod 59) =2 (\mod 59)$

$24 * (2 * 24^{57}) (\mod 59) =2 (\mod 59)$

Where $x = 2 * 24^{57}$.

Unfortunately I don't know if this x is the smallest one. How can I prove the fact in case it is correct?

Edit: Indeed, it is 5 not this huge value.

This is a problem in a chapter about Euler's theorem, thus I am pretty sure I can solve it merely using something related to it and modular arithmetic.

$\endgroup$
0
$\begingroup$

$59$ is prime, so $x^{-1} \pmod {59}$ exists and is unique. Stated differently, $\forall x \exists_1 y ~~xy \equiv 1 \pmod {59}$

Specifically, $24^{-1} \equiv 32 \pmod {59}$, so :

$$24x \equiv 2 \pmod {59}$$ $$\updownarrow$$ $$32\cdot 24x \equiv 32 \cdot 2 \pmod {59}$$ $$\updownarrow$$ $$x \equiv 5 \pmod {59}$$ $$\updownarrow$$ $$x = 5 + 59k,~ k \in \mathbb Z$$

Naturally $k=0$ and $x=5$ is the smallest, $k=1$ and $x = 64$ is the second smallest, etc.

$\endgroup$
0
$\begingroup$

Hint $\ $ By $ $ Gauss's algorithm, $\,\ {\rm mod}\ 59\!:\,\ 24x\equiv 2\iff x \equiv \dfrac{2}{24}\equiv \dfrac{1}{12}\equiv\dfrac{5}{60}\equiv\dfrac{5}1$

Beware $\ $ Modular fraction arithmetic is well-defined only for fractions with denominators coprime to the modulus. See here for further discussion.

$\endgroup$
  • $\begingroup$ Thanks, I think I should have mentioned that I am studying Euler's theorem, algorithm and primes function thus that's why I tried to solve it using the approach I used. I just edited my post, do you think there is any insight you can give me by not using Gauss' algorithm. $\endgroup$ – JOX Feb 6 '15 at 5:22
  • $\begingroup$ @JOX You could use repeated squaring to compute $\,24^{57}\!\pmod{59}.\,$ Generally Euler's theorem is not an efficient way to compute inverses. Better to use the Extended Euclidean Algorithm (or Gauss's Algorithm when the modulus is prime). $\endgroup$ – Bill Dubuque Feb 6 '15 at 5:38

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.