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

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

-

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

-
OK, I have $a_1 = a$, $m_1 = 100$, $gcd(m_1, m_2)=5$, $a_2 = a^2$, $m_2=35$, $gcd(m_1, m_3)=1$, $a_3 = 3a-2$, $m_3=49$, $gcd(m_2, m_3)=7$ From there I formed the equations: $$a \equiv a^2 (mod 5)$$ $$a \equiv 3a-2 (mod 1)$$ $$a^2 \equiv 3a-2 (mod 7)$$ The $(mod 1)$ is throwing me off being able to solve the equations from there, I feel like I've made a mistake in having that there. –  user142340 Apr 11 at 1:18
@user142340 Right, so you'll get some quadratics in $\,a,\,$ mod $5$ and $7$, each with two roots. By CRT they combine to yield $4$ solutions mod $35$. The (mod $1)$ equation can be ignored, since $\ j\equiv k\pmod{1}\iff 1\mid j-k\,$ is always true. –  Bill Dubuque Apr 11 at 1:22
@user142340 I solved the congruences to show how easy it is. –  Bill Dubuque Apr 11 at 3:40

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

-
That's not correct since, e.g. $\, a = 1\,$ yields the system $\, x\equiv 1\,$ mod $\,100,35,49,\,$ which is clearly solvable. –  Bill Dubuque Apr 11 at 1:44
This was the kind of approach I'd have been inclined to take intuitively myself, I follow the logic for the most part fairly easily. Though as Bill points out, $a=1$ should be a solution, but I can't see why this method doesn't give that. –  user142340 Apr 11 at 1:55
Where you have $100(49j+a-1)-a^2$, have you left out the $a$, as $x=100k + a$; so it would be $100(49j+a-1) + a -a^2$? –  user142340 Apr 11 at 2:20
I think that amendment tidies it up, $a=1$ becomes a solution then. We'd have $100(48j+a-1)+a-a^2 \equiv 0 (mod 35) \Longrightarrow 101a - 100 -a^2 \equiv 0 mod(35) \Longrightarrow -a^2 + 31a -30 \equiv 0 (mod 35)$ WA says this has solutions for $a=1, 15, 16, 30$, which seems to check out as far as I can tell. Is there a convenient method for work out those 4 values of $a$ by hand? –  user142340 Apr 11 at 2:38
Yes, consider $\pmod 7, \pmod 5$ separately. First, $a(a-1) \equiv 0 \pmod 5$ so $a \equiv 0, 1$. Then same process for $7$ and combining we should be able to arrive at the right answer. –  Sandeep Silwal Apr 11 at 2:53