How to solve polynomial modular equation to create a correct decryption algorithm I recently had a variant of the following problem in my cryptography course and I had trouble solving it and was looking to get some help. 

Given the symmetric key cryptosystem: $\text{KG, Enc, Dec}$ where $\text{KG}$ is a key generator that produces a random key in the space $Z_n = \{1, 2, 3, \ldots, n-1\}$, $m$ is a message from the space $Z_n$, and $\text{Enc}(K, m)$ is an encryption algorithm which computes ciphertext $c = (5m - 4k + 3) \bmod n$, design a decryption algorithm $\text{Dec}(K, c)$ such that it fulfills decryption correctness.

At first, I just tried solving for $c$ in $c = 5m - 4k + 3$, but realized that it does not account for $\bmod n$. Then it tried the following solution:

$$
\text{let} (d, x, y) = \text{extGCD}(c, n), m = (c\times x+4k-3)/5
$$

Where $\text{extGCD}$ is the Euclidian extended GCD function (essentially finding the modular inverse). That did not work either.

How would one go about solving this problem? What am I missing (so I can look into it further)?
We can write $m$ as 

$$m = (c -3 + 4k) \cdot 5^{-1} \pmod n$$

There is a problem here that the 5 may not has an inverse for every $n$. For example, it doesn't have an inverse in $\mathbb{Z}_{10}$.

It has an inverse in $\mathbb{Z}_{n}$ if $\gcd(5,n) =1$.

If it has the inverse one can find it by the Extended Euclidean Algorithm to form the Bézout's identity $5 x + n y = 1$ then take $\bmod n $ to achive the inverse as $5 x = 1 \bmod n$



As pointed by poncho, for finding the inverse of $5$ there is a better method $$(n+1)/5, (2n+1)/5, (3n+1)/5, (4n+1)/5$$ if the inverse exist. To see the inverse exist, one first needs to see that the $\gcd(5,n)=1$. 

In the general case, after some threshold, this approach may not be helpful, since testing all $$(n+1)/x, (2n+1)/x, \ldots, ((x-1)n+1)/x$$ will pass the calculation of the Bézout's identity.