Кіріспе
Бірдей қалдықтарды шешуге арналған теорема
Математикада, қытайлық қалдықтар теоремасы былай гласит: егер бүтін сан n-ді бірнеше санға еуропалық бөлудің қалдықтары белгілі болса, онда осы сандардың көбейтіндісіне n-ді бөлудің қалдығын бірегей түрде анықтауға болады, егер бөлгіштер жұп-жұп өзара жай (екі бөлгіштің ортақ факторы 1-ден басқа болмаса) болса. Мысалы, егер n-ді 3-ке бөлгендегі қалдық 2 болса, n-ді 5-ке бөлгендегі қалдық 3 болса және n-ді 7-ге бөлгендегі қалдық 2 болса, онда n-нің мәнін білмей, n-ді 105-ке (3, 5 және 7-нің көбейтіндісі) бөлгендегі қалдық 23 екенін анықтай аламыз. Маңыздысы, егер n табиғи сан және 105-тен кіші болса, онда 23 – n-нің жалғыз мүмкін мәні.
Теореманың ең ерте тұжырымы біздің заманымыздың 3-5 ғасырларында қытай математигі Суньцзи «Суньцзи Суаньцзин» еңбегінде жазылған. Қытайлық қалдықтар теоремасы үлкен бүтін сандармен есептеулер үшін кеңінен қолданылады, өйткені ол нәтиже мөлшерінің шегі белгілі болған есептеуді кіші бүтін сандар бойынша бірнеше ұқсас есептеулермен алмастыруға мүмкіндік береді. Қытайлық қалдықтар теоремасы (конгруенциялар түрінде берілген) кез келген негізгі идеалдық доменде дұрыс. Бұл кез келген сақинаға жалпыланды, екі жақты идеалдарды қолданатын формуламен.
Дәлел
Шешімнің болуы және бірегейлігі тәуелсіз түрде дәлелденуі мүмкін. Дегенмен, төменде келтірілген шешімнің алғашқы дәлелі осы бірегейлікті қолданады.
Бірегейлігі
x және y барлық конгруенциялардың шешімі деп есептейік. x және y санын ni-ге бөлгенде бірдей қалдық берсе, олардың айырмасы x − y әр ni-нің еселігі болады. ni өзара жай сандар болғандықтан, олардың көбейтіндісі N де x − y-ді бөледі, демек x және y сандары N модуль бойынша конгруэнтті. Егер x және y теріс емес және N-ден кіші болса (теореманың бірінші тұжырымында айтылғандай), онда олардың айырмасы N-нің еселігі тек қана x = y = 0 болған жағдайда ғана мүмкін.
Бар болуы (құрылыс дәлелі)
Барлықтың болуы x-тің нақты құрылымымен белгіленуі мүмкін. Бұл құрылысты екі қадамға бөлуге болады: біріншіден, екі модуль үшін мәселені шешу, екіншіден, модульдер саны бойынша индукция арқылы осы шешімді жалпы жағдайға дейін кеңейту.
Жүйелі іздеу
Х-тің мәні шешім екенін тексеру оңай: х-тің әр ni-ге бөлінгендегі қалдықты есептеу жеткілікті. Осылайша, шешімді табу үшін 0-ден N-ге дейінгі бүтін сандарды бірінен соң бірін, шешім табылғанша тексеру жеткілікті. Бұл әдіс өте қарапайым болғанымен, өте тиімсіз. Мұнда қарастырылған қарапайым мысал үшін, шешімді (яғни 39-ды) табу үшін 40 бүтін санды (0-ді қоса алғанда) тексеру қажет. Бұл экспоненциалды уақыт алгоритмі, себебі кіріс көлемі, тұрақты факторға дейін, N сандарының санымен, ал операциялардың орташа саны N ретімен шамалас. Сондықтан, бұл әдіс қолмен есептеуде де, компьютерлерде де сирек қолданылады.
Therefore, this method is rarely used, neither for hand written computation nor on computers.
Сіртеу арқылы іздеу
Ерітіндіні іздеуді просею арқылы едәуір жылдамдатуға болады. Бұл әдіс үшін, жалпылықты жоғалтпай, (егер олай болмаса, әрбір санды оның бөліністің қалдығымен алмастыру жеткілікті болар еді) деп есептейміз. Бұл шешім арифметикалық прогрессияға жатады дегенді білдіреді. Осы сандардың мәнін модуль бойынша тексеру арқылы, екі алғашқы конгруенцияның шешімін табамыз. Бұл сандардың мәнін модульдік түрде тексеріп, әрбір модуль тексерілгенше жалғастырсақ, шешім табылады. Модульдердің мәні кеміген ретпен орналасқан болса, яғни егер , онда бұл әдіс жылдам болады. Мысал үшін, бұл келесі есептеуді береді. Бірінші, 5 (ең үлкен модуль) бойынша 4-ке конгруэнтті сандарды қарастырамыз, олар: 4, 9 = 4 + 5, 14 = 9 + 5. Олардың әрқайсысы үшін 4 (екінші үлкен модуль) бойынша қалдықты есептеп, 4-ке модуль бойынша 3-ке конгруэнтті санды аламыз. Содан кейін, әр қадамда 20 = 5 × 4 қосып, тек 3 бойынша қалдықты есептеу арқылы жалғастыруға болады. Бұл төмендегідей нәтиже береді: 4 mod 4 → 0. Жалғастыру керек. 4 + 5 = 9 mod 4 → 1. Жалғастыру керек. 9 + 5 = 14 mod 4 → 2. Жалғастыру керек. 14 + 5 = 19 mod 4 → 3. Жарайды, енді 3 модуль бойынша қалдықтарды қарастырып, әр жолы 5 × 4 = 20 қосамыз. 19 mod 3 → 1. Жалғастыру керек. 19 + 20 = 39 mod 3 → 0. Жарайды, міне нәтиже. Бұл әдіс модульдердің көбейтіндісі тым үлкен болмаған жағдайда қолмен есептеу үшін жақсы жұмыс істейді. Дегенмен, модульдердің өте үлкен көбейтіндісі үшін бұл басқа әдістерге қарағанда әлдеқайда баяу. Жүйелі іздеуге қарағанда едәуір жылдам болғанымен, бұл әдістің экспоненциалдық уақыт күрделілігі бар, сондықтан ол компьютерлерде қолданылмайды.
By testing the values of these numbers modulo one eventually finds a solution of the two first congruences. Then the solution belongs to the arithmetic progression
Testing the values of these numbers modulo and continuing until every modulus has been tested eventually yields the solution. This method is faster if the moduli have been ordered by decreasing value, that is if For the example, this gives the following computation. We consider first the numbers that are congruent to 4 modulo 5 (the largest modulus), which are 4, 1=9 = 4 + 5, 1=14 = 9 + 5, For each of them, compute the remainder by 4 (the second largest modulus) until getting a number congruent to 3 modulo 4. Then one can proceed by adding 1=20 = 5 × 4 at each step, and computing only the remainders by 3. This gives
4 mod 4 → 0. Continue
4 + 5 = 9 mod 4 →1. Continue
9 + 5 = 14 mod 4 → 2. Continue
14 + 5 = 19 mod 4 → 3. OK, continue by considering remainders modulo 3 and adding 5 × 4 = 20 each time
19 mod 3 → 1. Continue
19 + 20 = 39 mod 3 → 0. OK, this is the result. This method works well for hand written computation with a product of moduli that is not too big. However, it is much slower than other methods, for very large products of moduli. Although dramatically faster than the systematic search, this method also has an exponential time complexity and is therefore not used on computers.
Негізгі идеалдық домендер
Қытайдың қалдық теоремасы үш түрлі жолмен тұжырымдалған: қалдықтар, конгруенциялар және сақина изоморфизмі арқылы. Қалдықтарға қатысты тұжырым, әдетте, негізгі идеалдық домендерге қолданылмайды, себебі мұндай сақиналарда қалдықтар анықталмайды. Дегенмен, қалған екі тұжырым негізгі идеалдық домен R үшін мағыналы: "бүтін сан" дегені "доменнің мүшесі" деп, ал дегені R-мен ауыстырылады. Теореманың осы екі тұжырымы осы контексте дұрыс, өйткені дәлелдер (алғашқы дәлелден басқа) Евклид леммасы мен Безу тождестігіне негізделген, олар кез келген негізгі доменде дұрыс. Алайда, жалпы алғанда, теорема тек қана болу теоремасы болып табылады және Безу тождестігінің коэффициенттерін есептеу алгоритмі болмаса, шешімді табуға ешқандай жол бермейді.
Реттік нөмірлеу
Қытай қалдық теоремасы тізбектер үшін Гёдель нөмірлеуін құруға қолданылды, бұл Гёдельдің толық еместік теоремаларын дәлелдеуде маңызды рөл атқарады.
Тез Фурье түрлендіруі
Басты факторлы FFT алгоритмі (Good-Thomas алгоритмі деп те аталады) қытайлық қалдық теоремасын пайдаланады. Ол белгілі бір өлшемдегі жылдам Фурье түрлендіруін есептеуді, егер және өзара жай болса, кішірек өлшемдегі екі жылдам Фурье түрлендіруін есептеуге дейін азайтады.
Шифрлау
RSA-ның көптеген іске асырылымдары HTTPS сертификаттарына қол қою және шифрлау кезінде қытайлық қалдық теоремасын пайдаланады. Қытайлық қалдық теоремасын құпияны бөлісуде де қолдануға болады, ол бір топ адамға үлестер жиынтығын таратудан тұрады, олардың бәрі бірге (бірақ ешқайсысы жеке алғанда) берілген үлестер жиынтығынан белгілі бір құпияны қалпына келтіре алады. Әрбір үлес конгруэнция түрінде көрсетіледі, ал конгруэнциялар жүйесін шешу қытайлық қалдық теоремасы арқылы қалпына келтірілетін құпия болып табылады. Қытайлық қалдық теоремасын пайдалана отырып, құпияны бөлісу үшін, белгілі бір кардиналдылықтан кем үлестер жиынтығынан құпияны қалпына келтіру мүмкін еместігіне кепілдік беретін бүтін сандардың арнайы тізбектері қолданылады.
Қалыптастырудың екіжақтылығы
Орта импульстік қайталау жиілігі радарымен қолданылатын қашықтық екіұштылығын шешу әдістерін қытайлық қалдық теоремасының арнайы жағдайы деп қарастыруға болады.