Describe all integers a for which the following system of congruences (with one unknown x) has integer solutions:

Question

$$x\equiv a \pmod {100}$$

$$x\equiv a^2 \pmod {35}$$

$$x\equiv 3a-2 \pmod {49}$$

I'm trying to solve this system of congruences, but I'm only familiar with a method for solving when the mods are pairwise coprime. I feel like there ought to be some simplification I can make to reduce it to a system where they are coprime, and then try to proceed from there, but I'm not sure how to go about it. Also, the fact that two are squares seems to suggest some kind of simplification in that direction.

Hopefully someone can point me in the right direction.

p.s. First time posting so formatting may have gone awry...

Answer 1

Hint $\ $ A solution exists of $\ x\equiv a_i \pmod{m_i}\iff a_i\equiv a_j \pmod{\gcd(m_i,m_j)}\ $ for all $\,i,j.$

This yields $\ {\rm mod}\ 5\!:\ 0\equiv a^2-a = \color{#c00}a(a-\color{#c00}1),\,$ $\ {\rm mod}\ 7\!:\ 0\equiv a^2-3a+2\equiv (a-\color{#0a0}1)(a-\color{#0a0}2).\,$

Hence the system is solvable iff $\ a\equiv \color{#c00}{0\ \ {\rm or}\ \ 1\pmod{5}}\ \ \ $ and $\ \ \ a\equiv\color{#0a0}{1 \ \ {\rm or}\ \ 2\pmod{7}}$.

This yields $4$ possible combinations $\ {\rm mod}\ (\color{#c00}5,\color{#0a0}7)\!:\,\ a\equiv (\color{#c00}0,\color{#0a0}1),\, (\color{#c00}0,\color{#0a0}2),\, (\color{#c00}1,\color{#0a0}1),\, (\color{#c00}1,\color{#0a0}2)$ which, by CRT, yields $4$ values mod $35,\,$ namely

$\quad {\rm mod}\ (\color{#c00}5,\color{#0a0}7)\!:\,\ a\equiv (\color{#c00}1,\color{#0a0}1)\iff \color{#c00}5,\color{#0a0}7\mid a-1\iff 35\mid a-1\iff a\equiv \ 1\ \pmod{35}$

$\quad {\rm mod}\ (\color{#c00}5,\color{#0a0}7)\!:\,\ a\equiv (\color{#c00}0,\color{#0a0}1)\iff \!a=\color{#c00}5n\ \ \&\ \ a\in \{\color{#0a0}{1,8,15,\ldots}\}\iff a\equiv \color{orange}{15}\pmod{35}$

$\quad {\rm mod}\ (\color{#c00}5,\color{#0a0}7)\!:\,\ a\equiv (\color{#c00}0,\color{#0a0}2) = (0,1)+(0,1)\iff a\equiv \color{orange}{15}+\color{orange}{15}\equiv 30\pmod{35}$

$\quad {\rm mod}\ (\color{#c00}5,\color{#0a0}7)\!:\,\ a\equiv (\color{#c00}1,\color{#0a0}2) = (1,1)+(0,1)\iff a\equiv \ 1\ +\color{orange}{15}\equiv 16\pmod{35}$

Answer 2

Fixed Had some arithmetic errors. From first, $x = 100k+a$. Then from the third, $100k+a - 3a+2 \equiv 0 \pmod {49} \implies 2k-2a+2 \equiv 0 \implies k \equiv a-1 \implies k = 49j+a-1$. Then plug into second.

$100(49j+a-1)-a^2 \equiv 0 \pmod {35} \implies 100a-100-a^2 \equiv 0 \implies -a^2+30a-30 \equiv 0 \pmod {35}$

WA says this has no solutions. I still dont know how I missed $a \equiv 1$..