I'm given $x^2$ ≡ -1 mod 365
I know that 365 = $5*73$ so then my congruence becomes,
$x^2$ ≡ -1 mod 5 and $x^2$ ≡ -1 mod 73
Since $(-1)^2$ ≡ 1 mod 5 and $(-1)^{36}$ ≡ 1 mod 73 implies that there exist solutions and since d = 2 for both then I know there are 2 solutions for both mod 5 and mod 73 (so 4 total solutions, right?)
my problem is that I'm not sure how to solve the linear congruence that I'm left with
If my solutions for mod 5 are $x_0$, $x_1$ and mod 73 are $y_0$, $y_1$
I think i'm suppose to solve the linear congruence in the form
- x ≡ $x_0$ mod 5 , x = $y_0$ mod 73
- x ≡ $x_0$ mod 5 , x = $y_1$ mod 73
- x ≡ $x_1$ mod 5 , x = $y_0$ mod 73
- x ≡ $x_1$ mod 5 , x = $y_1$ mod 73
Am I suppose to apply the Chinese Remainder theorem to solve? If so how do I know what my $x_0$, $x_1$ and $y_0$, $y_1$ are in the first place? If anyone can point me in the direction to solve that would greatly appreciated.
It comes down to solving for $x$ when you have $x \equiv a \pmod 5$ and $x \equiv b \pmod{73}$
The "brute force" solution looks like this.
\begin{align} x &= 5m + a \\ x &\equiv b \pmod{73} \\ \hline 5m + a &\equiv b \pmod{73} \\ 5m &\equiv b-a \pmod{73} \\ m &\equiv 44(b-a) \pmod{73} \\ m &= 44(b-a) + 73n \\ \hline x &= 5(44(b-a)+73n) + a \\ x &= 220b - 219a + 365n \\ x &\equiv 220b - 219a \pmod{365} \\ x &\equiv 146a - 145b \pmod{365} \end{align}
$x^2 \equiv -1 \pmod 5 \implies x \in \{2,3\}$
$x^2 \equiv -1 \pmod{73} \implies x \in \{27,46\}$ {I used Wolfram Alpha to solve this.}
\begin{array}{r|r|r} x \mod 5 & x \mod{73} & x\mod{365} \\ a & b& 146a-145b \\ \hline 2 & 27 & 27\\\ 3 & 46 & -27\\ 2 & 46 & -173\\ 3 & 27 & 173\\ \end{array}