Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

Any advice?

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

share|improve this question

1 Answer 1

up vote 0 down vote accepted

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.