Sunday, January 24, 2016

elementary number theory - A simple modular arithmetic query.

Given $a,b,c\in\Bbb N$ with $\mathsf{gcd}(a,b)=\mathsf{gcd}(b,c)=\mathsf{gcd}(c,a)=1$ we know that there are $m_1,m_2,m_3\in\Bbb N$ such that $a\equiv m_1a^2\bmod abc$, $ab\equiv m_2ab\bmod abc$ and $b\equiv m_3b^2\bmod abc$ holds.


It is also easy to see there is a single $m$ such that $$a\equiv ma\bmod ab,\quad b\equiv mb\bmod ab$$ holds.


However how to find a single $m$ coprime to $c$ such that $$1\equiv ma\bmod abc,\quad 1\equiv mb\bmod abc$$ holds?



At least how to find a single $m$ such that $$\ell_1 a\equiv ma^2\bmod abc, \quad \ell_2 ab\equiv mab\bmod abc,\quad\ell_3b\equiv mb^2\bmod abc$$ holds where $0<\ell_1,\ell_2,\ell_3<\log abc$ holds and at least one of $\ell_1,\ell_2,\ell_3$ is distinct?


If not how small can we make $\max(\ell_1,\ell_2,\ell_3)$ where $a\nmid\ell_1$ and $b\nmid\ell_3$ holds?

No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...