Masala modular arithmetic (qoldiqli arifmetika) bo'yicha. Deylik, a va b sonlari olinib (a <= b < n), bu sonlar ko'paytmasini n ga bo'linganida c qoldiq chiqadi, ya'ni a * b = c (mod n). Endi savol: berilgan n soni uchun ko'paytmasida c qoldiq qoladigan nechta (a, b) pair tanlash mumkin. Masalan, ko'paytmasini 7 ga bo'lganda 5 qoldiq qoladigan (ya'ni n = 7, c = 5) jami 3 ta pair tanlash mumkin: (1, 5), (2, 6), (3, 4).
Deylik, f(n, c) shunday kombinatsiyalar sonini sanaydigan funksiya bo'lsin. Masalan, f(7, 5) = 3. Endi berilgan n soni uchun c ning har bir qiymatida (c = 0...n-1) f(n, c) funksiyasining natijalarini olaylik. Masalan, n = 6 uchun bu natijalar
(8, 2, 3, 3, 4, 1) ko'rinishida.Bir qarashda bu tuple random ko'rinadi. Aslida tajribamdan maqsad ham shu tupleni o'rganish. E'tiborimni tortgan joyi, n 2 dan katta tub son bo'lganida (1e4 gacha bo'lgan sonlar uchun tekshirib ko'ra oldim, ixtiyoriy tub son uchun deya olmayman) tupledagi distinct elementlar soni 3 tagina: n, n/2 va n/2+1 (/ bu yerda integer division). Masalan, n = 10 uchun tuple
(14, 3, 6, 2, 7, 5, 7, 2, 6, 3) ga teng. Ancha tartibsiz va tushunarsiz. Lekin n = 11 uchun (11, 6, 5, 6, 6, 6, 5, 5, 5, 6, 5) tuple ancha sodda: bu yerda faqat 11, 5 va 6 sonlari bor. Original masala shartiga qaytadigan bo'lsak, ko'paytmasini 11 ga bo'lganda ixtiyoriy c qoldiq qoladigan 2 ta son tanlashning 5, 6 yoki 11 ta usuli bor.Meni qiziqtirayotgan savol, nega aynan 3 ta? n soni borligi tushunarli, lekin nega n/2 va n/2+1 sonlari ham bor? Nega boshqa sonlar yo'q?