← All problems

Visser’s Open Question 8.29 on restricted versus full division

Over weak arithmetic PA−\mathrm{PA}^{-}, let pa17\mathrm{pa17} denote the full Euclidean division principle ∀a,b∈N (b>0→∃q,r∈N (a=bq+r∧r<b))\forall a,b\in\mathbb{N}\,(b>0\rightarrow\exists q,r\in\mathbb{N}\,(a=bq+r\land r<b)), and let pa17−\mathrm{pa17}^{-} denote its restriction to coprime pairs, namely the same assertion under the additional hypothesis gcd⁡(a,b)=1\gcd(a,b)=1. The problem asks whether PA−\mathrm{PA}^{-} proves pa17−→pa17\mathrm{pa17}^{-}\rightarrow\mathrm{pa17}; equivalently, whether pa17−\mathrm{pa17}^{-} and pa17\mathrm{pa17} have the same strength over PA−\mathrm{PA}^{-}.

Equivalent formulations
  1. Does restricted Euclidean division for coprime pairs have the same strength as unrestricted Euclidean division over PA−\mathrm{PA}^{-}?

    source: Equivalence of Restricted and Full Division

References

Source: arXiv

Progress summary

Refreshed
Open · solution reported

An unrefereed preprint claims to settle the question by showing that restricted and full division have the same strength.

Visser’s Open Question 8.298.29 asks whether restricted Euclidean division is as strong as unrestricted division in weak arithmetic. The latest preprint claims an affirmative answer over PA−\mathrm{PA}^{-}, but no independent assessment was found.

Recent preprint

Naoya Kato’s Equivalence of Restricted and Full Division claims a quotient-preserving reduction from arbitrary division instances to coprime pairs. If correct, this proves equivalence of restricted and full Euclidean division over PA−\mathrm{PA}^{-} and settles the question; the claim remains unverified.

Current status (as of October 2026): An unrefereed preprint claims the question is solved affirmatively over PA−\mathrm{PA}^{-}, but the result is not independently verified.

Sources

Solutions 0

No solutions have been posted yet.