Say I want to decide if an integer is a square. My integer is rather big so I can't keep it in memory altogether, but I know that it is a product
$$f = \prod_{i=1}^nf_i, f_i\in \mathbb{N}$$ Then I remember something like this which may be useful $$(ak+b)^2 \equiv b^2\mod a$$ I also know that for a product each factor modulo can be multiplied together and then modulied again. This can be seen as in th expression : $\prod(ka_i+b_i)$, only term not any k:s in it will be the last term: $\prod b_i$
I know that if I do modulo on the product and it is not $b^2$ mod $a$, then I can say that it is not a square. But can I be sure to select such an $a$ or do I have to try all the $a$s in the world?