# Demostrating that a number x is the smallest such that 24x mod (59) = 2 mod (59)

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.

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

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.

• 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. – JOX Feb 6 '15 at 5:22
• @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). – Bill Dubuque Feb 6 '15 at 5:38