Simple question about modular arithmetic

80 Views Asked by At

I am trying to understand if I could know something about the following relationship:

If I have:

$b \equiv n \mod a$

$d \equiv n \mod b$

$n \gt 0$

Is it possible to know something about the direct relationship of $a$ and $d$ or a combination of both?

$d \equiv ??? \mod a$

or other combinations, for instance, like:

$bd \equiv ???\mod ab$

I have been trying trial-error samples, and I am not sure if the usual rules of modular arithmetic could be applied somehow to get that direct relationship, so I am getting lost. Any hint or help is very appreciated, thank you!

UPDATE:

By reviewing directly the definitions of modularity:

$b = a*k_1+n,\ k_1 \in \Bbb N, k_1 \gt 0$

$d = b*k_2+n,\ k_2 \in \Bbb N, k_2 \gt 0$

thus,

$d = (a*k_1+n)*k_2+n = a*k_1*k_2+n*k_2+n = a*k_3+n*(k_2+1)$

$k_1*k_2=k_3 \in \Bbb N, k_3 \gt 0$

finally:

$d \equiv n(k_2+1) \mod a$

2

There are 2 best solutions below

1
On BEST ANSWER

Use the definitions:

$$b \equiv n \pmod a \iff \ \exists \ p \ \in \mathbb Z \ / \ b = pa + n$$

And:

$$d \equiv n \pmod b \iff \ \exists \ q \ \in \mathbb Z \ / \ d = qb + n$$

If you want to discover a property, proceed from here. Use techniques like comparing the different expressions of $n$, multiplying the two equations with each other, etc.

3
On

If $a$ and $b$ are relatively prime, then you can say something about bd mod ab.