# Question regarding solving a modulo equality

Two Equations:

1. ab % c = d

2. (ci + d) % c = d, i $\in \mathbb N$

I want to solve for b given the above two equations with a, c, and d known.

ab = ci + d

b = (ci + d) / a

i = (k + an), n $\in \mathbb Z$: n >= 0

b = (c(k+an) + d) / a

Again, since a, c, and d are known - and n can be any Integer >= 0 - the matter is solving for k.

An example.

(29 * 77) % 72 = 1

(72 * (31 + 77 * 0) + 1) = 2233 and 2233 % 72 = 1

(72 * (31 + 77 * 1) + 1) = 7777 and 7777 % 72 = 1

(72 * (31 + 77 * 2) + 1) = 13321 and 13321 % 72 = 1

-

$ci+d \equiv d \pmod c \implies ci \equiv 0 \pmod d$. Then choose $i$ such that $\gcd(i,d) = 1$ so it follows that $c = dk$ for some integer $k$.

Then $ab \equiv d \pmod c$ or $ab \equiv d \pmod dk$. Then $d|ab$ is the only information that we can gather without extra conditions.

-