0

i should solve $a\cdot 57 \equiv_{39} 1$ for $a\in \mathbb Z$

My first idea was:

$a\cdot 57 \equiv_{39} 1 \ \ \Leftrightarrow \ \ 39 | (a\cdot 57 - 1 ) \ \ \Rightarrow \ \ a\cdot57-1=n\cdot 39\ \ \forall n \in \mathbb N \setminus \{0\}$

so we get: $a=\frac{n\cdot 39 + 1}{57},\quad \forall n \in \mathbb N \setminus \{0\}$

but since $a\in\mathbb Z$ this doesn't work.

Another approach would be splitting it into equivalence system of equations such that I can use the CRT, but that seems too much of a hassle for this exersice.

Another approach, also a bit CRT like, would be saying: There exists an x such that $0\leq x < 39$ then $a=x+39$. So we would get $57-39=18$ and we would have to solve $18x\equiv_{39} 1$ but this isn't really easier to calculate.

So, what's the fastest approach here?

xotix
  • 887

1 Answers1

1

I don't know if this is the fastest method, but a systematic way would be the Euclidean algorithm. Properly done, it yields numbers $a,n\in \mathbb{Z}$ such that $$57a+39k=1.$$

EDIT: Applying the Euclidean algorithm, you will finde $\mathrm{gcd}(57,39)=3$, hence $57$ is not invertible in $\mathbb{Z}/39\mathbb{Z}$ and there certainly cannot be $a,n\in \mathbb{Z}$ such that the above equation holds.

asdq
  • 3,900