Корнакия алгоритмі - Cornacchias algorithm - Wikipedia

Жылы есептеу сандарының теориясы, Корнакия алгоритмі болып табылады алгоритм шешуге арналған Диофантиялық теңдеу , қайда және г. және м болып табылады коприм. Алгоритмді 1908 жылы Джузеппе Корнакия сипаттаған.[1]

Алгоритм

Біріншіден, кез келген шешімді табыңыз (мүмкін тізімделген алгоритмді қолдану арқылы Мұнда ); егер ондай болмаса бар, бастапқы теңдеудің алғашқы шешімі болуы мүмкін емес. Жалпылықты жоғалтпай, біз мұны болжай аламыз р0м/2 (егер жоқ болса, онда ауыстырыңыз р0 бірге м - р0, бұл әлі де тамыр болады -г.). Содан кейін Евклидтік алгоритм табу , және тағы басқа; тоқтаған кезде . Егер бүтін сан болса, онда шешім болып табылады ; әйтпесе басқа түбірін қолданып көріңіз -г. шешім табылғанға дейін немесе барлық тамырлар таусылғанша. Бұл жағдайда қарабайыр шешім жоқ.

Қарапайым емес шешімдерді табу үшін (х, ж) қайда gcd (х, ж) = ж ≠ 1, мұндай шешімнің бар екендігі оны білдіретініне назар аударыңыз ж2 бөледі м (және баламалы түрде, егер бұл болса м болып табылады шаршы жоқ, онда барлық шешімдер қарабайыр). Сонымен, жоғарыда аталған алгоритмді қарабайыр шешімді іздеу үшін пайдалануға болады (сен, v) дейін сен2 + дв2 = м/ж2. Егер мұндай шешім табылса, онда (гу, gv) бастапқы теңдеудің шешімі болады.

Мысал

Теңдеуді шешіңіз . Square6 (мод 103) квадрат түбірі 32, ал 103 ≡ 7 (мод 32); бері және , шешім бар х = 7, ж = 3.

Пайдаланылған әдебиеттер

  1. ^ Корнакия, Г. (1908). «Su di un metodo per la risoluzione in numeri interi dell 'equazione ". Giornale di Matematiche di Battaglini. 46: 33–90.

Сыртқы сілтемелер