Issue with the linear congruence of 56x \equiv 70 modulo 455

35 Views Asked by At

I am trying to solve the linear congruence relation $56x \equiv 70$ mod $455$. The GCD of $56$ and $455$ is 7, so we can reduce it to the form $8x \equiv 10$ mod $15$. The Euler totient function of $15$ is 8, so we know that $8^8 \equiv 1$ mod $15$. From here is where I begin to struggle, I have tried the following: $8^{-1}=8^7=8^{2 * 3}* 8 = 64^3*8$ which I think equals $-11^3 * 8$, but from here I am stuck, any advice on how to proceed?

2

There are 2 best solutions below

0
On

we have $$x\equiv \frac{70}{56}=\frac{5}{4}\equiv \frac{460}{4}\equiv 115 \mod 455$$

0
On

From $8x\equiv 10\mod{65}$, you need to find the multiplicative inverse of $8$. Since $8\cdot 8\equiv -1$, the multiplicative inverse of $8$ is $-8$, so that $x\equiv -8\cdot 10 = -80\mod{65} \equiv 50\mod{65}$.