XXNNが互いに素ならX,2X,...,NX(modN)X, 2X, ..., NX (\bmod N) は全て異なる値になります。 したがって、XXNNが互いに素のとき全ての寿司を食べることができます。 ただし、XXが最大で101010^{10}になることから、全てのXXを順番に調べると無限に時間がかかってしまいます。

そこでNNを素因数分解し、オイラーのφ関数を使って計算することで計算量を減らします。 例えば N=12=2×2×3N=12=2 \times 2 \times 3 なら互いに素な整数の個数は 12(112)(113)12(1-\frac{1}{2})(1-\frac{1}{3}) で計算できます。 この計算には2の倍数でない数が全体の12\frac{1}{2}あり、その中で更に3の倍数でない数が23\frac{2}{3}ある、という有名な説明があります。 素因数分解がボトルネックとなり全体計算量は O(N)O(\sqrt N) となります。