Confusion about why the reduction of non-linear congruence seems to require only a single choice of prime power $p_i^{k_i}$

58 Views Asked by At

I have a question about solving non-linear congruences :

So say that we have $f(x)\in \Bbb Z[x]$, and we want to solve $f(x)=0(\mod{p_1^{k_1}….}p_n^{k_n}$. My lecture notes tell me that this can be reduced to solving $f(x)=0\mod{p_i^{k_i}}$. So in other words we only have to choose one prime power number in the factorisation. This confuses me somewhat though. All the numbers are prime so are all coprime to each other so it's not as if they would simply cancel when we reduce $\mod{p_i^{k_i}}$. I would have assumed that in such a question we would have to reduce to $f(x)=0\mod{p_i^{k_i}}$, except that we would have to do this for each $i$ and then use the Chinese remainder theorem to get a full result. Could anyone please explain this to me please ?

1

There are 1 best solutions below

1
On BEST ANSWER

You wrote

My lecture notes tell me that this can be reduced to solving $f(x)=0\mod{p_i^{k_i}}$. So in other words we only have to choose one prime power number in the factorisation.

In these sorts of cases, this doesn't necessarily mean just one specific value of $i$. Instead, as you wrote later, you have to do this for all $i$ since, otherwise, you can certainly get results which don't solve $f(x) \equiv 0 \pmod{(p_1^{k_1}\ldots p_n^{k_n})}$. In your case, perhaps it was just an oversight for the notes to not explicitly specify what the $i$ stood for. Alternatively, in certain contexts, as a shortcut where it's assumed to be understood, this may not be stated explicitly but, instead, is assumed implicitly.

One important thing to note is that the notes do not explicitly state another option, e.g., something like that it is for just one $1 \le i \le n$. This means the interpretation of what the $i$ represents is left up to the reader to determine, with it assuming the context is sufficient for this. Nonetheless, I prefer to have these sorts of details always explicitly stated, to help avoid any possible confusion and mistakes.