Chinese Remainder Theorem (I think?)

[PhDorBust]

Given system of congruences,

$$x^3 \equiv y_1 \mod n_1$$
$$x^3 \equiv y_2 \mod n_2$$
$$x^3 \equiv y_3 \mod n_3$$

You are given $$y_1, y_2, y_3, n_1, n_2, n_3$$. The $$n_i$$'s are pairwise relatively prime. Solve for x.

I think there might be a connection between the fact that the exponent of x is 3 and there are 3 congruences given. But I haven't the slightest idea how to approach.

For each of them you also know there exists a d such that $$y_i^d \equiv x \mod n_i$$ but I don't think that is so useful.

 

[lippyka]

The solution to this system of congruences can be found using the Chinese Remainder Theorem (CRT). This theorem states that, given any two relatively prime integers and a pair of congruences with those moduli, there exists a unique solution for the congruences. Furthermore, if there are more than two congruences with pairwise relatively prime moduli, then there is a unique solution for all of them. Therefore, in this case, since the moduli n_1, n_2, and n_3 are relatively prime, the CRT can be used to find a unique solution for the system of congruences. To apply the CRT, first calculate the product of the moduli, i.e. n = n_1n_2n_3. Then, for each modulus n_i, calculate the inverse of n/n_i modulo n_i. That is, find an integer d_i such that (n/n_i)d_i \equiv 1 \mod n_i. Finally, the solution x to the system of congruences is given by the formula:x \equiv \sum_{i=1}^3 y_i(n/n_i)d_i \mod n.