The iterated mod problem (Q1119390): Difference between revisions

Let \(a,b_ 1,...,b_ n\) be integers. The iterated mod problem is the question whether \[ ((...((a mod b_ 1) mod b_ 2)...)mod b_ n)=0. \] In this problem the mod normalizes such that \(0\leq c mod d<| d|\). It is shown that this problem is P-complete. This problem has some resemblance with the Euclidean algorithm for computing the gcd. However, for the gcd, it is not proved to be P-complete. It is shown that in the case that the a and \(b_ i\) are polynomials in \({\mathbb{Q}}[x]\), then the solution of the iterated mod-problem is in NC, which contains (presumably) faster parallel algorithms than those that are P-complete.