Thursday, 11 May 2017

congruences - Simple question about modular arithmetic



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$



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.


No comments:

Post a Comment

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...