Теорема1. Если F - поле, |F|=q,
![](data:image/gif;base64,R0lGODlhKQARAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAIAAQAmAAwAhQAAAAAAAAAAHR0AAAAAMx0AMgAcSAAdSB0dSAAzWwAzWh1GbDIAHTMAADMeRzNdXTNbgEgcAEgdHVozAEYzRkZGM1lZf1l/WUhuf11/f0Rqe113d2xGHW5GRn9ZSH9uSH9/XXtqRHd3XXd3ZmZ3d2aIiIBbM4iIZgECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwZkQIBwSCwaj8ikcgkIOJ8BpvQoKC6mWACnaMoCBk9CcnJNcgJVAxfLGCKMkYSw4SWaoMZJEVJsQANiSApDZUOBQgVGDlN0SYNCEUcSUiYCGEh6c1FHh2OPSE5iDZ1EUKRfTgdIQQA7)
,
![](data:image/gif;base64,R0lGODlhJwATAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAIAAwAiAAwAhQAAAAAAAB0AHQAAHR0AAAAAMx0AMgAcSB0dSAAzWh1GbDMAADMAMzNdXTNbgEgcAEgdHVozAEZGM1lZf1l/WV1/f0huf2xGHX9/XX9uSHtqRHd3XWZ3d3d3ZmaIiIBbM4iIZgECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwZlQIBwSCwaj8ikEhkIOJbQY0G4eEavj+HneoQcBUTw8BIYAA5LhZRYFT4S1GNz3jROhwthpGg97pF3ABkET4EABkoISWJCYnBuR2R0TY9DWUIXengBSpVIaABtAE1TC4ZEDFFNVkEAOw==)
, то
![](data:image/gif;base64,R0lGODlhNQAVAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAIAAgAwAA8AhQAAAAAAAB0AABwcHAAAHQAAMx0AMh0dSAAcSAAdSB00NAAzWh1GbDMAADNdXTNbgEgdAEgcAEceM1ozHVozAFszM0ZGM1lZf1l/WV1/f0huf0Rubl13d2xGHW5GM39uSH9/XXd3XXd3ZmZ3d2aIiIBbM4iIZgECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwZ0QIBwSCwaj8ikcjmEFJjQqHQqFSgORwl1CzAAOlwmggoJmBNCLbcRGEfd4SQ82QkMkJQAmtuZfwMEAH5xS3MRC0INRGVUeWaPAYhEfUMURQ+EUnBPQ16ZUJRCkgARnwCQj0dulokBplAUcGZPDZyvSGyAGkEAOw==)
.
Cледствие. При условиях теоремы любой
![](data:image/gif;base64,R0lGODlhKQARAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAIAAQAlAAwAhQAAAAAAAAAAHR0AAAAAMwAcSAAdSB0dSAAzWgAzWx1GbDIAHTMAADMeRzQ0HTNbgEgcAEgdHUgdAFozAEYzRkhuf11/f0Rqe113d2xGHW5GM25GRn9ZSH9uSH9/XXtqRGZ3d2aIiIBbM4iIZgECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwZgQIBwSCwaj8ikMpkJOJ+BwnJqFAmo2KSU+MgCBk8CcpIUBa7CQFGEXVwAnyQCkPAWoXNjZ6A4MqABYkZkQhlJEEgNVAxTGgB5RRFUaHZEgkkTkEdqQhIBfUZQl0JgnEdBADs=)
удовлетворяет уравнению
![](data:image/gif;base64,R0lGODlhRQAVAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAIABABAAA0AhQAAAAAAAB0AABwcHB0AHQAAHR0AMgAAMx0dSAAcSAAdSB00NAAzWh1GbDMAADQ0HTNbgEgcAEgdAFozHVozAFszM11/f0huf113d2xGHW5GM39uSH9/XXd3XWZ3d2aIiIBbM4iIZgECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwaJQIBwSCwaj8ikcqkULBDMqHRqNAAy1CwzEIBov+DhQeiYJsLoyBDEzAQGaDSBOAeAAoVhIC7EX+wBClljQw5eQwwAiUMSe2EMWEYUXJRci0KEZEQbAg1Rk5WWRwJhmQACh0JqfEWrX3VCsAAaiqxED0mhXK1DkbZKUGBnAGV9jAGeaG6Xjl9ch0EAOw==)
Теорема2. Пусть F - поле, |F|=q,
![](data:image/gif;base64,R0lGODlhKQARAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAIAAQAmAAwAhQAAAAAAAAAAHR0AAAAAMx0AMgAcSAAdSB0dSAAzWwAzWh1GbDIAHTMAADMeRzNdXTNbgEgcAEgdHVozAEYzRkZGM1lZf1l/WUhuf11/f0Rqe113d2xGHW5GRn9ZSH9uSH9/XXtqRHd3XXd3ZmZ3d2aIiIBbM4iIZgECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwZkQIBwSCwaj8ikcgkIOJ8BpvQoKC6mWACnaMoCBk9CcnJNcgJVAxfLGCKMkYSw4SWaoMZJEVJsQANiSApDZUOBQgVGDlN0SYNCEUcSUiYCGEh6c1FHh2OPSE5iDZ1EUKRfTgdIQQA7)
,
![](data:image/gif;base64,R0lGODlhJwATAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAIAAwAiAAwAhQAAAAAAAB0AHQAAHR0AAAAAMx0AMgAcSB0dSAAzWh1GbDMAADMAMzNdXTNbgEgcAEgdHVozAEZGM1lZf1l/WV1/f0huf2xGHX9/XX9uSHtqRHd3XWZ3d3d3ZmaIiIBbM4iIZgECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwZlQIBwSCwaj8ikEhkIOJbQY0G4eEavj+HneoQcBUTw8BIYAA5LhZRYFT4S1GNz3jROhwthpGg97pF3ABkET4EABkoISWJCYnBuR2R0TY9DWUIXengBSpVIaABtAE1TC4ZEDFFNVkEAOw==)
. Если n – порядок элемента a, то n|(q-1).
Теорема3. Пусть F – поле, |F|=q, тогда
![](data:image/gif;base64,R0lGODlhLwAYAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAMABAAqABAAhQAAAAAAAB0AAB0dAB0AHQAAHR0AMgAAMwAdMgAcSB0dSB00NAAzWh1GbDMAADIAHTIAMjMzWzNbgEgdHUgcAFozAEgzM1szM0ZGRll/WV1/f1luf0huf2xGHX9uSH9/XXd3XXtqRGZ3d2aIiIBbM4BuboiIZgECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwZ1QIBwSCwaj8ikcskEGACOprRpAUSm2OMEQMp6v+BklOgIACphgbkSOCgFDUDHXQzY72bkYyABUJIUDEOCYQhDFHFHdH5hQn1CBEhoQh0FRmx4doRFEEOTSIJdCmEenotHanKNAHdYHGFbWZ1ho1NlAZtYmFJBADs=)
, p – простое,
![](data:image/gif;base64,R0lGODlhKwARAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAIAAQAnAAwAhQAAAAAAAAAAHR0dAB0AAB0AHRwcHAAAMwAcSAAdSB0dSAAzWwAzWh4zRx1GbDMAADMAHTIAHTIAMjMeRzNGbjNbgEgdAEgcAEgdHVozHVozAFszM0YzRkhIW0hbSEZGbll/WUhuf11/f0Rqe113d2xGHW5GM39ZSH9/XX9uSHd3ZmZ3d2aIiIBbM4iIZgECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwZvQIBwSCwaj8ikcgl4BIqWwJNJLQqKmapWaBowtkaCNHBYloeUobgCuAQcxZY2/RiaihIABGy8AzQIR3IbQyFFTmNkSykFQmlDGgZDCkYTfBcMfkN1QiVHGFQnVkoRSGdbnERwQgRJiadCLVKwmkJBADs=)
.
Cледствие. Если F – конечное поле, то оно имеет характеристику p – простое натуральное число, таким образом содержит подполе, изоморфное
![](data:image/gif;base64,R0lGODlhFQAZAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAIABAARABIAhAAAAAAAAAAAHR0AAB0AHQAAMwAcSAAzWh1GbDMAADIAMjMeRzMzWzNGRjNGbjNbgEgcAFozAEhZf11/f0huf2xGHX9/XX9uSHtqRG5/WXd3XWaIiIBbM4iIZgECAwECAwVBICCOZFlGQaoWZgtEgitKYxU8cjkgOZkcvRHEEByxioAYMlByyAYlgiyhUpUSACiSyCguABykSLEUUIpdZEIpCgEAOw==)
.
Теорема о примитивном корне (4). Элемент группы называется примитивным корнем, если его степени 0,1,2,… пробегают все элементы группы. Cуть теоремы в том, что в поле F из q элементов найдётся элемент а , что каждый ненулевой элемент поля представляет степень а, т.е. a – примитивный корень, и порядок элемента а равен q-1.
Теорема 5. Пусть F – поле и
![](data:image/gif;base64,R0lGODlhJAAVAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAIAAgAeAA8AhQAAAAAAAB0AHR0AAAAAHR4eAB4AHgAAMx0AMgAdMgAdSB0dSAAzWh1GbDIAHTMAADIAMjMAMzQ0HTNbgEgcAEgdAEgdHVozAF1/f113d0huf1luf2xGHW5GM3d3XX9/XX9uSHtqRGZ3d2aIiIBbM4iIZgECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwZ9QIBwSCwaj8gkRJlEkg5NgEATJS6riOqwoeUUBwHAJQAVOowBwjAszBYLW8ATyQDUh48JMTGkDMtGA1xED0QXQyBTAByARX5FD4MAV2J3AI1DHXaQRAt/USRHIEQcAaaWQodEbAAVAZKoVEhnVZQAnk0GUYVrAQpREUnBQ0EAOw==)
- нормализованный полином из F[х]. Тогда существует таккое содержащее
F поле
K, что в
К[x] полином
![](data:image/gif;base64,R0lGODlhJAAVAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAIAAgAeAA8AhQAAAAAAAB0AHR0AAAAAHR4eAB4AHgAAMx0AMgAdMgAdSB0dSAAzWh1GbDIAHTMAADIAMjMAMzQ0HTNbgEgcAEgdAEgdHVozAF1/f113d0huf1luf2xGHW5GM3d3XX9/XX9uSHtqRGZ3d2aIiIBbM4iIZgECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwZ9QIBwSCwaj8gkRJlEkg5NgEATJS6riOqwoeUUBwHAJQAVOowBwjAszBYLW8ATyQDUh48JMTGkDMtGA1xED0QXQyBTAByARX5FD4MAV2J3AI1DHXaQRAt/USRHIEQcAaaWQodEbAAVAZKoVEhnVZQAnk0GUYVrAQpREUnBQ0EAOw==)
разлагается в произведение линейных сомножителей. Это поле К называют полем расщепления для
![](data:image/gif;base64,R0lGODlhJAAVAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAIAAgAeAA8AhQAAAAAAAB0AHR0AAAAAHR4eAB4AHgAAMx0AMgAdMgAdSB0dSAAzWh1GbDIAHTMAADIAMjMAMzQ0HTNbgEgcAEgdAEgdHVozAF1/f113d0huf1luf2xGHW5GM3d3XX9/XX9uSHtqRGZ3d2aIiIBbM4iIZgECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwZ9QIBwSCwaj8gkRJlEkg5NgEATJS6riOqwoeUUBwHAJQAVOowBwjAszBYLW8ATyQDUh48JMTGkDMtGA1xED0QXQyBTAByARX5FD4MAV2J3AI1DHXaQRAt/USRHIEQcAaaWQodEbAAVAZKoVEhnVZQAnk0GUYVrAQpREUnBQ0EAOw==)
. К примеру,
C – поле расщепления для любого полинома из Q[x].
Пусть
![](data:image/gif;base64,R0lGODlhKQARAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAIAAQAmAAwAhQAAAAAAAB0AAAAAHR0AHR0AMwAAMwAdSAAcSB0dSAAzWgAzWwA0SB1GbDMAADMeRzQ0HTNbgEgcAEgdAEgdHVozAEYzRkZGM11/f0huf0Rqe113d2xGHW5GM39uSHd3XX9/XXtqRGZ3d3d3ZmaIiIBbM4iIZgECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwZoQIBwSCwaj8ikUskJOBuAZmBJPZamw0J1W0QMD1yiwBkwICVChzUwGGKHpaqHcDErFYBFuMheegRQRg5kTnZFFQAThmdID1VqiV5IHQB4RhRVhpB7AItHEpZCAkZvEwGBfGSeZG5kgUEAOw==)
- корень некоторого ненулевого полинома из
F[
x]. Тогда элемент
х называют алгебраичным над F. Иначе – трансцендентным.
Теорема 6. Пусть
![](data:image/gif;base64,R0lGODlhKwARAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAIAAQAmAAwAhQAAAAAAAB0AAAAAHR0AHR0AMwAAMx0AMgAdSAAcSAAzWwAzWgA0SB1GbDMAADMeRzNdXTNbgEgcAEgdAEgdHVozAEYzRkZGM1lZf1l/WV1/f0Rqe113d2xGHX9uSHd3XX9/XXtqRHd3ZmZ3d2aIiIBbM4iIZgECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwZuQIBwSCwaj8ikUtkJOBuAZmBJPZamw0J1W0wMEVyiwBkwICVCR7I5AHiJpaqHcDGfFelwMdBGVooRRQ5kTnZFfxOGRYoHRg9VagATb0ULQ2hGFFWGkUR/aVhGikcSlkMCRoUADqNDhKNkrmRQAEEAOw==)
алгебраичен над
F. Тогда существует единственный неприводимый нормированный полином
![](data:image/gif;base64,R0lGODlhVAAVAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAIAAgBQAA8AhQAAAAAAAB4AHh0AAAAAHR0AHQAdPgAAMx0AMx0AMgAdMgAdSAAcSB0dSR0dSAAyMgAzWgAzWwA0SB1GbD0dADMAADIAHTMAHTMAMzIAMjQeSDMeRzQ0HTMzSDNbgEgcAEgdAEgdHVozAFszAEYzRkZGM0hbSFtuSF1/f113d0Rqe0huf2xGHW5GM3d3XX9/XX9uSHtqRG5/WWZ3d3d3ZmaIiIBbM4iIZgECAwECAwECAwECAwECAwECAwECAwECAwb/QIBwSCwaj8ikcslsFjFKqDMZqA6rBkp1sawypoDDEiYAIwPHz5QFzjgT5iLrCxBxhR/IlM4UrY8xA1UBYkkTABVFak5sQhVoAAOFkkIWRgEEQjYBdwBwRDadSwVhRnlFmJqcQ3wAJkMnRYVyAI1EFR5xAJuZpkdstkLBCkMPrLWzRQNHibeDVclFEiDRAKdGy0Z0IgQrdYV+QtVDuUUVh3HNAK3WSeVDtouIQ2674wAceuZFIU6zFa2uFcmnTYiDY0L0eLNk5NDBFkvuFdEHIBAfeUQcAoAorKOQEUNGBEA3Al2tABGEgIA0JOWlQdUG3XmGhyILlCpZCmG3REWTHnq6lGBcEqxJmSXqgiYRyISnUgBSniZZqfOXFQBBAAA7)
, что
![](data:image/gif;base64,R0lGODlhPQAVAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAIAAgA5AA8AhQAAAAAAAB0AHR0AAAAAHR4AHgAAMx0AMgAdMgAcSB0dSAAyMgAzWh1GbDMAADIAHTIAMjMAMzMeRzMzSDNdXTNbgEgcAFozAEZGM0hbSFlZf1tuSFl/WV1/f113d0huf2xGHW5GM3d3XX9/XX9uSG5/WXd3ZmZ3d2aIiIBbM4iIZgECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwa2QIBwSCwaj8ikcnmEKJ3MZSAQLRqWJEEVeQU4Klso87AtWoiJ6mULKg+zn6HWSwUMunfhAxkgYIpkbgBdQl9DGUMbVkcMhQ1EhkRTk1NFKYReQwhDC0NpIJhCjUJnkIKDRANCFwRxF11rQqGEJEYOj2VwcqRDDkNQl0QXowAWxIVFF5STx8VoQgqeQ41xe0SjDnWnRmleYG2rQ8q4F7hCU1cOoc1llW5xTGLbpwVMvvP4SxH5RkEAOw==)
, и каждый полином
![](data:image/gif;base64,R0lGODlhUQAVAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAIAAgBNAA8AhQAAAAAAAB0AHQAAHR0AAB0dAAAAMx0AMgAdMgAcSB0dSAAzWh1GbDIAHTMAADIAMjMeRzQ0HTNbgEgcAEgdHVozAEYzRl1/f0huf0Rqe1luf113d2xGHW5GM25GRn9ZSH9/XX9uSHtqRGZ3d26AbmaIiIBbM4iIZgECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwb/QIBwSCwaj8ikcslsAh5JqDMZqFoDCcCkmkVyuE6TYSnATJGDIkM77TKly8PZyHETJ4tm3blmcpIEVmNIfUUTbUSBABUBgwANRQFpQlhDckZ2SZBCCnd5QiaSQ5VCmQAFQ2tidAB/RQ4SRRZNoVaGR3mfQ5kIQ4dCjolHDkYOV41HFbqFWrpDBMytdhVDIWWtwUSxr9EQTcRCH7dGv0V2cMpD2UIRw0YUTZNHeEYRzqVEncBLa50d1UdWLbl3p4gJACGGmMEn5EuVe9QaBvi0pQhBSoKKBCJFTtdEIVsK7VGoqQmcOUvKMXGjL4mAJeBQMqHXpAsYJSeL5JSZZEuABCVgggAAOw==)
с корнем
а делится на
m(x). Этот полином называют минимальным полиномом элемента
а над
F.
Разложение полиномов на множители в конечных полях. Любой полином степени n в
![](data:image/gif;base64,R0lGODlhKwAZAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAIABAAmABIAhQAAAAAAAAAAHR0AAB0AHQAAMwAdSAAcSB0dSAAzWgAzWx1GbDMAADIAMjMeRzQ0HTMzWzNGRjNGbjNbgEgcAEgdAFozAEhZf11/f0huf2xGHX9ZM25GM39/XX9uSHtqRHd3XW5/WXd3ZmZ3d2aIiIBbM4iIZgECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwaaQIBwSCwaj8iiJcBsFpAUZlKokSYtgiQlMS0eiJdhdaLtEjXJwWK6NQ+/RoaiSymWAllhQHykGMxtRlxzRHBET4BHHmpFaEV5gFxGdUaGAHtEEmVGHACSfEMDRQRsn0UIlUIMTU1FDACiQpRDmAAVAWtUbkN/ELKmXZZTDgAlQ7NmjrsADUO3AX9TTNFmeBnL2EO+2dwMkNxEQQA7)
может быть разложен на множители за конечное число шагов, так как существует
![](data:image/gif;base64,R0lGODlhFQAYAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAIABAARABAAhQAAAAAAAB0AAB4eAB0AHR0AMgAAMwAdMgAdSB0dSAAzWh1GbDMAADIAHTIAMjMzWzNbgEgdHUgcAFozAEgzM1szM0ZGRll/WV1/f1luf0huf2xGHX9uSH9/XXtqRGZ3d2aIiIBbM4BuboiIZgECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwZFQIBwSCwaj5zChbE4Gi3OKATQjA6bFeswC2AgiIIAYBIwaIWDq/YwlGgnQw5BY3UMJwptYmi2bgKAeWd0Z0J7hQCAX2dBADs=)
возможных полиномов степени <n, но такой алгоритм "проб и ошибок” чрезмерно трудоёмкий(этот алгоритм осуществляется через PDF). Так что неплохо бы иметь более быстрые алгоритмы.
Если взять полином
![](data:image/gif;base64,R0lGODlhrAAZAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAIABACoABEAhQAAAAAAAB0AHR0AAAAAHR0dAB0AMgAAMwAdMgAcSB0dSAAdSAAzWh0zWh1GbDMAADIAHTIAMjQ0HTMzWzNGbjNbgEgdHUgcAEgdAEceM0geNFozAFszAFozHUgzM1szM0ZGRll/WV1/f0huf113d1luf2xGHW5GM39uSH9/XXtqRHd3ZmZ3d2aIiIBbM4BuboiIZgECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwb/QIBwSCwaj8ikcslsOp/QqHRKrSYNgId1y+06I0mwl+oBTMbotPWwFKiflrd8zhQvsXSkq5np9ul/ahtPDHlKDwlJgYaMSQMBFQABbEIQI0UBBJcuAYkoeFQXAQFJmZudT4tVqkaipEamAJyJRqyYkEoQBUIXQ5RFJgAmhUNaRRujyaPERANDDknBAMyNQrZDzkLQRsPSSNcAA9DeR3tE479F2UQP21HGTetMyMrLUfT11FnxRxz19sXcPXEjJB2RXkXgRTGoBGEUcF4YHnG48MuQQUJcSAQgwciDSETwKdOnT0lHKRBTJdGHgeFJRUfIYSqiQMiGdBCOQKt5YggogygmKJmghWQngJ7VrCEJKmSoUiM1YR75tWBIAwAdiCTTOcREAGavhFVxNQSFkHbCvg4J68QWhiFvhcQ9Ag7DqJhqhbAtoqFUAHfetsVJkrMOGhBJ36RMo2IJCgGXknxME0lg4stAn9EjisQOI2gfMHtZvOVqVtFLQmfhjFoKMtZqXgUBADs=)
, то его производная
![](data:image/gif;base64,R0lGODlhnAAZAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAIAAgCYABMAhQAAAAAAAB0AHR0AAAAAHR0dABwcHAAAMx0AMgAdMgAcSB0dSAAzWh1GbDMAADIAHTIAMjMeRzQ0HTMzWzNGbjNbgEgcAEgdHUgdAEceM1ozAFszAEgzM1szM0ZGRkhbSEZGbll/WV1/f0huf113d1luf2xGHW5GM39uSH9/XXtqRHd3ZmZ3d26AbmaIiIBbM4BuboiIZgECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwb/QIBwSCwaj8ikcslsOp/QqHRKrTotB6t2y+16v+CoKRsuHxEAR+OYMbuLjCfkPfUAQvT80UIkKwV6TxcVQxYBhwoAbYGMSmiNSmsdU4uQU2tOcZZGk2mJRRoBn2xdlVMDAYQBfkMPRS8BBEMBQyiPUqiEhpgAhrRIsSMAsKNUpm6+Sg8FQnxFrERxmkMORqGH2AHTQ3OuRANNJgAm25tFx99ML0W8QtBCKAPtQmpT650AwtVO4FbX2dqmADxUZB8UQETGIHFWkIoGA0MWuHvC0BypI++OzBGiAeOREwDKpSFE5F+2cgbFCRGZRIIXdGBYQpMIQENGb05uVfGmcFwxWyNrJIK0eO5ITxM/iWBL0lFpoQC8VF4a0q8XQXj01pgIKOSXFphCRomNguHqEFMXmuBcsvGNHaJuKql4glCJA5J0CM2Dy2XRtaRI2moMJImv4cMAOjkAjFigkCAAOw==)
равна нулю тогда и только тогда
![](data:image/gif;base64,R0lGODlhLQAYAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAIABAApABAAhAAAAAAAAB0AHR0AAAAAMwAcSAAzWh0zWh1GbDMAADIAMjMzWzNbgEgcAEgdHUceM1ozAFszM0YzRl1dRl1/f0huf113d2xGHX9/XX9uSHd3XXd3ZmZ3d2aIiIBbM4iIZgVpICCOZGmeaKqu6hUEJsHOsZjQOMqMRe6LAlIQkAjsRI3Xr+SRjW6ix2gwg7yuL0PJaTs+l6gmiSpCiLjg0hAocoy0JskJez15ewCF6OK84NMieFAAMEhKJH8/LoWAjY6PAAuQMx4BZpAhADs=)
для каждого i. Это будет выполнено в случаях
p|i или
![](data:image/gif;base64,R0lGODlhKQAYAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAIABAAlABAAhAAAAAAAAB0AHR0AAAAAMwAcSAAdSAAzWh1GbDMAADMzWzNbgEgcAFozAFszM0YzRl1/f0huf113d2xGHX9/XX9uSHtqRHd3XXd3ZmZ3d2aIiIBbM4iIZgECAwECAwECAwVcICCOZGmeaKqu4hQEbJwSYiLf5DIW+C2QvxHj1TNtaCObaDBCpBqv6OtQQtZ0yuLpSGICrFpTUBSkmh4nafSkE/EmyIkhXOIBskMYya516emAgT0KgisbAU6FACEAOw==)
для каждого i. Поэтому
![](data:image/gif;base64,R0lGODlhQAAVAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAIAAgA7AA8AhQAAAAAAAB0AHR0AAAAAHR4eAB4AHgAAMx0AMgAdMgAcSAAdSB0dSAAzWh1GbDMAADIAHTIAMjMAMzMeRzQ0HTNbgEgcAEgdAEgdHVozAEZGbl1/f113d0huf1luf2xGHW5GM3d3XX9/XX9uSHtqRGZ3d2aIiIBbM4iIZgECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwa3QIBwSCwaj8ikcln8HIgRZZS5DASow8bwuRR0sEfuo0K1DKdMBLhoHirWGfBnPRx5hwLi4JoJcAEaQhBGAQRDAQtDanQAfwAPRgVDDkWOQ3NzRWNFVp1WRSeOkEQJQ22XlkMDR6N0jqtDcUJ2X0SpQ2SalGu0eFCxWpVIFKxFfZ5WwaaXb0MMW0eDRpTPIHWMbkKbQh+dytOXAcEXV0TfdJ9FtUoQ61LYSs9UBkyt8ISI90QS+kdBADs=)
если
![](data:image/gif;base64,R0lGODlhJAAVAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAIAAgAeAA8AhQAAAAAAAB0AHR0AAAAAHR4eAB4AHgAAMx0AMgAdMgAdSB0dSAAzWh1GbDIAHTMAADIAMjMAMzQ0HTNbgEgcAEgdAEgdHVozAF1/f113d0huf1luf2xGHW5GM3d3XX9/XX9uSHtqRGZ3d2aIiIBbM4iIZgECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwZ9QIBwSCwaj8gkRJlEkg5NgEATJS6riOqwoeUUBwHAJQAVOowBwjAszBYLW8ATyQDUh48JMTGkDMtGA1xED0QXQyBTAByARX5FD4MAV2J3AI1DHXaQRAt/USRHIEQcAaaWQodEbAAVAZKoVEhnVZQAnk0GUYVrAQpREUnBQ0EAOw==)
- полином от
![](data:image/gif;base64,R0lGODlhFAAVAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAIABAAQAA0AhAAAAAAAAB0AAAAAHQAdSB0dSAAzWh1GbDMAADIAMjMeRzQ0HTMzWzNGRjNZfzNbgEgcAEgdAFozAF1/f0huf2xGHW5GM39/XW5/WXd3XX9uSGZ3d2aIiIBbM4iIZgECAwUxICCOZGmeCCCcJwEwLKnEZUebwTB2+RiMsJMBMBQhdCaN4HAbQZoiCxFK/YkiAeYpBAA7)
. Теперь несколько обобщим данную ранее теорему о НОД(
![](data:image/gif;base64,R0lGODlhJAAVAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAIAAgAeAA8AhQAAAAAAAB0AHR0AAAAAHR4eAB4AHgAAMx0AMgAdMgAdSB0dSAAzWh1GbDIAHTMAADIAMjMAMzQ0HTNbgEgcAEgdAEgdHVozAF1/f113d0huf1luf2xGHW5GM3d3XX9/XX9uSHtqRGZ3d2aIiIBbM4iIZgECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwZ9QIBwSCwaj8gkRJlEkg5NgEATJS6riOqwoeUUBwHAJQAVOowBwjAszBYLW8ATyQDUh48JMTGkDMtGA1xED0QXQyBTAByARX5FD4MAV2J3AI1DHXaQRAt/USRHIEQcAaaWQodEbAAVAZKoVEhnVZQAnk0GUYVrAQpREUnBQ0EAOw==)
,
![](data:image/gif;base64,R0lGODlhJwAVAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAIAAgAiAA8AhQAAAAAAAB0AHR0AAAAAHR4eAB4AHgAAMx0AMgAdMgAdSB0dSAAzWh1GbDIAHTMAADIAMjMAMzMeRzQ0HTNbgEgcAEgdAEgdHVozAEZGbl1/f113d0huf1luf2xGHW5GM3d3XX9/XX9uSHtqRGZ3d2aIiIBbM4iIZgECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwaEQIBwSCwaj8gkwHMgQpRPpZExbEoFHOmwMoxqEdoiJiz0FAcBACZgBWSEDmOAMAwohuBiYdgotolmZkUPFEQJW0VMSANHD0RjQiJYfkmFg31CXhhUlEcTjUQLVUdxRn2iH0MigAGtnEeYSwGcFmlErwBZUg66Ul4AomEGWo51dmRSEURBADs=)
):
Теорема. Пусть K - область с однозначным разложением на множители, произвольной характеристики . И пусть
![](data:image/gif;base64,R0lGODlhJAAVAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAIAAgAeAA8AhQAAAAAAAB0AHR0AAAAAHR4eAB4AHgAAMx0AMgAdMgAdSB0dSAAzWh1GbDIAHTMAADIAMjMAMzQ0HTNbgEgcAEgdAEgdHVozAF1/f113d0huf1luf2xGHW5GM3d3XX9/XX9uSHtqRGZ3d2aIiIBbM4iIZgECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwZ9QIBwSCwaj8gkRJlEkg5NgEATJS6riOqwoeUUBwHAJQAVOowBwjAszBYLW8ATyQDUh48JMTGkDMtGA1xED0QXQyBTAByARX5FD4MAV2J3AI1DHXaQRAt/USRHIEQcAaaWQodEbAAVAZKoVEhnVZQAnk0GUYVrAQpREUnBQ0EAOw==)
- примитивный полином в K[x], отличный от константы. Возьмём его однозначное разложение на множители
![](data:image/gif;base64,R0lGODlhEQEZAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAIABAAMAREAhgAAAAAAAB4AHh0AAAAAHR4eAB0AHQAAMx0AMh0AMwAdMgAdMwAdSAAcSB0dSB0zWgAzWgAzWx1GbB1IbjIAHTMAADMAHTMAMzIAMjQ0HTMzWzNGRjNGbjNZfzNbgEgcAEgdAEgdHUceM1ozAFszAFozHVszM0gzM1tISEhIW0ZGRlV7VVl/WV1/f113d0Rqe0huf1luf2xGHW5IHWxGM25GM39ZM25GRnd3XX9/XX9uSHtqRG5/WWZ3d3d3ZmaIiIBbM4BuboiIZgECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwf/gACCg4SFhoeIiYqLjI2Oj5CRkpOUlZaXmJmakTIBEpugigGhpJqdn5kXiaqWAQEMqY+sgzoAO5OzpYO5gw8AHLqhvITDhbW3hjOukAeLApUfhs2T04rPg9eCIwHTN4/V1M6E2drcggMewQDgkuyG5OSC5okNjhiNCJUQmfeS+doAgETqF6wWoX+DOgBIpw5TMUMJaBUiETCRDEcjHu2T9GEjgBGoImV0dJGQxwARII2kBLKRDI8APCpL2bAlS42DZsAcJWhDPAD1Bg0IoHAeAAowCgUgkBTIKwA6EEbySOHQ0KLuBCUltLTpU0EIo1raSmvoR6OGqnIl8CLgVwBh/xPRCKa20FUAaAshVcrWLSyxg6QOuqiiUElCFAoIiiYo60UZNAVVMETClWVXkQEwDpj1aIF0mwl1hnB4UAWGACYbUr2oc+LFIQkBcfc4c2pCrAlV7nxpNqLEoBM5BgAZt3FEw4IKEkjok4zOA1bHxtn4EPNB058jir4a93SSnRcMCl0oK/dCuSt8b5j1uqD12q1KN/2otCEDgzqTv81xY/xCKwGAnzSI7JdaSLktMkBmWQU4oCH/EWKgevQ9sqAkFwoS4SAB/pQfIiB0Z9p6iCgHAEEr+XZIBquhJkhll2FWiEdZofjhcp2xKKJkLj6ioiI0VcDTjYXoiB5uPTa0zv8hNiLyY5EtVuhSIQ5oA05dzQFQZQ2BTRIaloaM4FoiVRYilWCQgClImUsSQtBRhnyy5UF0KlmIBYqIqQiehkygJQBcChLRIIM6YqJlh4TUSWRD2geJRxQZgighIhSiKEqDDClIZI5Gkp1ltlGWE6byFMLpJSEKkioAqyISqVLLEBJRgiEpc9JgptZHSAh7NvImJB0RwucgvB5SqbCO5PLQI8MKUqwjza5CjJ2HRPusIScAoAGyjCgbSVDIJKKDAG0lcpo+hWQTriHH0kLuIuklGcm45f7p5CEeHscjtfgOsm4hvLoH1bvmopYgIyXBCIsiy6LqysKCqKKwLAxPC8okxIfAZPEh3vKLHAAYy1ZxIw0f8rDHpGiKsiTKuCLvykoeTG0gADs=)
.Пусть
![](data:image/gif;base64,R0lGODlhKwAYAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAMABAAmABAAhAAAAAAAAB0AAB0AHQAAMwAdMh0dSAAcSAAdSAAzWh1GbDMAADIdADIAMjMzWzNbgEgcAFozAFszM0YzRl1/f0huf2xGHX9uSH9/XXd3XWZ3d2aIiIBbM4iIZgECAwECAwVoICCOZGme6CkE7JO+ZGsaowDfhLi4d29CI85pofC9BiRkqQA4GFG50U4UCfCIKZaWZYrqRJYS8NkdXQQupZRsUgOUXhEiVd2yEuJRWBQgzdkmTgBTAHUBRVSAMVaKjSgSjpGSJn2TIiEAOw==)
, если
![](data:image/gif;base64,R0lGODlhSwAYAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAIAAwBHABEAhQAAAAAAAB4AHh0AHR0AAAAAHR4eAAAAMx0AMgAdMwAcSAAdSB0dSAAzWgAzWx1GbDMAADIAHTMAHTMAMzIAMjMeRzQ0HTMzWzNZfzNbgEgcAEgdAEgdHVozAFszAFszM0YzRkZGbl1/f113d0huf1luf0Rqe2xGHW5GM3d3XX9/XX9uSHtqRHd3ZmZ3d2aIiIBbM4iIZgECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwbgQIBwSCwaj8ikcslsEg/OqHR61Ewn1OIpEMhWiTDoUuAViiFlYiWLKGeGivTxEW1kB0T8UMM9rghdHQFiRRFFMAEFQ11CK21TYURoQpMAcUcRBkIadEWERXYORZVCHlynXKJPkptDHUkJe0efQ3+dkrdOkUMEQooAEKpGr0N6RCe0skakUcYAely0IEnC02ZHKAB2o29EqKdH3ZbXQmRHDEPJQoZRj1SXlRt9RJcAW6lF9cSLQ/K3J2XuSeHgRIITCnKmoHNiTgkEcQmRXCjFZcGRiUawRCyDKNeRjhvLBAEAOw==)
, в противном случае
![](data:image/gif;base64,R0lGODlhKAAYAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAMABAAjABAAhAAAAAAAAB0AAB0AHQAAHQAdMwAAMwAcSB0dSAAdSAAzWh1GbDMAADMdADIAMjMzWzNbgEgcAFozAFszM0YzRl13d0huf11/f2xGHX9uSH9/XXd3ZmZ3d2aIiIBbM4iIZgVZICCOZGmeKCkELJS+YnQiowC/THDcPIqhjEUPtjMVAMWh6UeSBFyA4MnJqgYUpyRzJFMuSYMSw5sdGUqJlLV62gICpDS5JElSA0KRZB5lEfiAJBOBhIVwhSEAOw==)
. Тогда НОД(
![](data:image/gif;base64,R0lGODlhJAAVAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAIAAgAeAA8AhQAAAAAAAB0AHR0AAAAAHR4eAB4AHgAAMx0AMgAdMgAdSB0dSAAzWh1GbDIAHTMAADIAMjMAMzQ0HTNbgEgcAEgdAEgdHVozAF1/f113d0huf1luf2xGHW5GM3d3XX9/XX9uSHtqRGZ3d2aIiIBbM4iIZgECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwZ9QIBwSCwaj8gkRJlEkg5NgEATJS6riOqwoeUUBwHAJQAVOowBwjAszBYLW8ATyQDUh48JMTGkDMtGA1xED0QXQyBTAByARX5FD4MAV2J3AI1DHXaQRAt/USRHIEQcAaaWQodEbAAVAZKoVEhnVZQAnk0GUYVrAQpREUnBQ0EAOw==)
,
![](data:image/gif;base64,R0lGODlhJwAVAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAIAAgAiAA8AhQAAAAAAAB0AHR0AAAAAHR4eAB4AHgAAMx0AMgAdMgAdSB0dSAAzWh1GbDIAHTMAADIAMjMAMzMeRzQ0HTNbgEgcAEgdAEgdHVozAEZGbl1/f113d0huf1luf2xGHW5GM3d3XX9/XX9uSHtqRGZ3d2aIiIBbM4iIZgECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwaEQIBwSCwaj8gkwHMgQpRPpZExbEoFHOmwMoxqEdoiJiz0FAcBACZgBWSEDmOAMAwohuBiYdgotolmZkUPFEQJW0VMSANHD0RjQiJYfkmFg31CXhhUlEcTjUQLVUdxRn2iH0MigAGtnEeYSwGcFmlErwBZUg66Ul4AomEGWo51dmRSEURBADs=)
)=
![](data:image/gif;base64,R0lGODlhEAEZAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAEAAwANARIAhgAAAAAAAAAAHR0AHR4AHh0AAB4eAAAAMx0AMh0AMwAdMgAdMwAdSAAcSB0dSB0zWgAzWgAzWx1GbDMAADIAHTMAHTIAMjMAMzQ0HTMzWzNGRjNGbjNZfzNbgEgcAEgdAEgdHUceM0g0AEk0AFozAFozHVszHVszAEE0AFszM0gzM1tISEhIW0ZGRkhZf1l/WUhuf11/f113d0Rqe1luf2xGHW5IHW5GM25GRn9uSHd3XX9/XXtqRG5/WWZ3d26AbmaIiIBbM4BuboiIZgECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwf/gACCg4SFhoeIiYqLjI2Oj5CRkpOUlZaXmJmNAQIwmp+anKCjpI+ipaiCNQESqa6Mq62vs6MBox4BtoQWlbyOvoM5ADyNIpPApMiHwsSMxrSDF7TShg8AG40jibkNgh4QhQeV4osDhOaEAeSDH7kBDAAeHQDWOI/rk/iIBIT8hCTqBBUQ1I5bPEHWABSY50pfJIeF/AmSKAigw4IBun1AqKjbwV29GgkjhGAQCQBBFlkrEUkZqpKITqZcASDFoZXQALgcNXJQgkIcADBMZM3EIo/fTFY66agGuEFPAehSNGGqI6aUSMhqFLVGoQBREVXNiXWS1kZOCUW1ARaAV4qE/8YK0gDXLdJCngwVCDAvoCEKeQdx8hTk3SCYAHq6Ciwox14AFhNRKFRYgOBghRAbmtHoxivGCgME9YtoMqHKlwUhVlwIHiwALQ55BBAVoiAKBrwdgug1bdzfhiY0Es7INm5vW0/bBhcWAHFBE4YOOkE6EXXbmSDinuchUZDlACIAh56IGiPzhO6qsp2SUHK3tgcGj/seVA3bCgZ1RxS//oStz+X0yH2GtDdIfYP0V0iA/5WCVG2NoBMOIvstCOAoBYQFUVkSFkLgIRWO5xyCl2QoiYmEOMRhIh8aEiJ0F5JSg3oo2QYMVut8hwgGhzAo3Sg6LhJVVVtB5Flzzg0VoP6AjQQJUkWLGEnbgnH9qMmDg5hmiAMVrRMCIVq6BwCXnh1G0ithDsKlIA4BkyZKgqx5pplMQvKmSdjdVmCcmc1JCo2CIOhOIV+KqUpbglg1pSq0vLdKLkgCwBKU6bDDyiBeqUXLRgSx08h7gxryQoOCnPCVpVt1lQqWWRoCgiN3HoLMTqSk+eojFfzyZJ2Q5DrIrYfEZoivi6CHnn2AJkZAYM0cUmgwyy7iIy05RMunIj/WFZySvEpSLWfNIjLPe9qKGN2qghlmCEDqEnrIsYUYyyu7rh0SKbyEyNstJSgYdEgrNhmCryD6ksJWRpgoum8tuSzssCEBTzDbw4gEAgA7)
.
Доказательство данной полностью аналогично доказательству уже доказанной теоремы.
На этой теореме также основана некоторая модификация алгоритма PSQFF, но перед этим нужно доказать ещё две вспомогательные теороемы.
Теорема 1. Пусть
![](data:image/gif;base64,R0lGODlhJAAVAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAIAAgAeAA8AhQAAAAAAAB0AHR0AAAAAHR4eAB4AHgAAMx0AMgAdMgAdSB0dSAAzWh1GbDIAHTMAADIAMjMAMzQ0HTNbgEgcAEgdAEgdHVozAF1/f113d0huf1luf2xGHW5GM3d3XX9/XX9uSHtqRGZ3d2aIiIBbM4iIZgECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwZ9QIBwSCwaj8gkRJlEkg5NgEATJS6riOqwoeUUBwHAJQAVOowBwjAszBYLW8ATyQDUh48JMTGkDMtGA1xED0QXQyBTAByARX5FD4MAV2J3AI1DHXaQRAt/USRHIEQcAaaWQodEbAAVAZKoVEhnVZQAnk0GUYVrAQpREUnBQ0EAOw==)
- полином в
![](data:image/gif;base64,R0lGODlhLAAZAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAIABAAmABIAhQAAAAAAAAAAHR0AHR0AAB4AHgAAMx0AMgAdSAAcSB0dSAAzWh1GbDMAADIAHTIAMjMAMzMeRzQ0HTMzWzNGRjNGbjNZfzNbgEgcAEgdAFozAEhZf11/f113d0huf2xGHW5GM3d3XX9/XX9uSHtqRG5/WWZ3d2aIiIBbM4iIZgECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwaZQIBwSCwaj8iiJsBsGpLDR1IKBWgEVcATOjBuhp/ApUqtHpIERlWTHS6OjXe7GMACUAEEYHTEJNpbRR8LH0UNRoFQH4lEBEYNakN2gEgYj0QBRRVJKIxDEo9jAI5EXVAOR2oKRWcADU1NhqNFkQBhcgCZQoVzAHoTRKhZZVkRd0YFHlANor3EQxBJ0b25AsrU2MDY2w2T20RBADs=)
. Тогда
![](data:image/gif;base64,R0lGODlhbQAYAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAIABABoABAAhQAAAAAAAB0AAB0AHR4AHgAAHR4eAAAAMx0AMgAdMgAdSAAcSB0dSAAzWh1GbDMAADIAHTIAMjMAMzMeRzQ0HTMzWzNGRjNZfzNbgEgcAEgdAEgdHVozAE4zAF1/f113d0huf0Rqe1luf2xGHW5GM39/XXd3XW5/WX9uSGp7VXtqRGZ3d2aIiIBbM4iIZgECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwb/QIBwSCwaj8ikcslsOp/Q5QMgiFqZ0yoyEwgonpFkmNhdEDnfytU5XqaFbWEmelgOiqPiBNBaN+tMe31CKAREGQ1gTQhFZkVxfkeQS5CMck8cT4lCeWQFIJFJmU4Bn3hEm0MCAQAcAYAAEEWlQ15DlkKOAGqhVKyusLKzBUItAWa8R5ZzRhAGGADMALCoAKlCU5xDD6ZIrl3gAddDztDS1EN5nQDcSQ/m4wAJQxkOACPoQgL2RQ/8ALp6DZknxx4+JFqaZJNGBJqQO0LyRTuS7Z5AIw4BQJyWJKMUe4geDRkV0QgJa0YqAnwSDpykkUNaSARAIR6ShUVQjKQmLGYSWFzrLuoUwoHnEXsMAJx0EpJMFyMc/rESoiHAvxHXAgp0WSRqOnFUpy7ZxBDAhiWgoAQVeFZJ2itxriVVYkjJu0YXhcxNUteKyqqsOjy9OGKwwG95iUggEgQAOw==)
.
Доказательство:Пусть
![](data:image/gif;base64,R0lGODlhKAAXAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAIABAAjABAAhQAAAAAAAB0AHR0AAAAAHR4eAB4AHgAAMx0AMgAdMgAdSB0dSAAzWh1GbDIAHTMAADIAMjMAMzQ0HTNbgEgcAEgdAEgdHUceM1ozAF1/f113d0huf1luf2xGHW5GM3d3XX9/XX9uSHtqRGZ3d2aIiIBbM4iIZgECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwaKQIBwSCwaj8ikcslcHpaCpvQYmhYxjWaHQRwEJoDA8+goBggbQCmgGCKKjoKQciyNiR0hl/gglopZRnddR31IUUYdg0N0Rg+BABBDGEMVg4tCEoVEC0IYgxdEZYAAnR5Eb0MBq0uUQh0Be2FFshZJoaJNkkIiVgAGS4YAGKttR7hFEUnKUsTGvkJBADs=)
,
![](data:image/gif;base64,R0lGODlhYAAZAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAIABABbABIAhQAAAAAAAB4AHgAAHR0AAB4eAB0AHQAAMx0AMgAdMgAdSB0dSAAzWgAzWx1GbDIAHTMAADMAHTMAMzIAMjMeRzQ0HTMzWzNGRjNZfzNGbjNbgEgcAEgdHUgdAFozAFozHVszAEYzRltISEhZf11/f113d0Rqe0huf1luf2xGHW5GM39ZM25GRnd3XX9/XX9uSHtqRG5/WWZ3d3d3ZmaIiIBbM4iIZgECAwECAwECAwECAwECAwECAwECAwECAwECAwb/QIBwSCwaj8ikcslsOo+Sp1ToCVivB2Z0Os0uBVykZ8D0KsFh4aT5SgNGw1RAs1wz22mPlHEkYJcEDkt6TilFfhgAAWZHJ0UBA441AQpDCEU1UhANYZBCk5VCl0QPBUIbSYxxACmcRBBuG6FLqkIpDIZFsEM1CUSCRim1QgRHu0MQV1bDQsxFwkjFRscAHnRCBqlIG9evwFNkTs7GRHbVrwG8zBXkRBxN6UQZSTXr7UILVLXmD0eC+SqIjCIyDoC0IdmU9DPyD0BAS0SuJHEk5JscV4qKYIz4B52yeK8uBBpiMQBGkEIwvnsSwYk5N0c8zBLSssnLJZmIvECjhBrMLiTfAAgwseQYCCszi/AxsgVJ059JngqRWoRqEjlWukGFWSXc1q9gw4odW9QrzCAAOw==)
.Тогда
![](data:image/gif;base64,R0lGODlh9wAwAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAIAAgDyACsAhQAAAAAAAB0AAB0dAB0AHR4AHgAAHQAAMwAdMh0AMh0AMx0dSAAcSAAzWh0zWgszbR1GbB1MfxVAgDMAADIAHTMAHTIAMjMAMzMeRzQeSDQ0HTMzWzNGRjNGbjNZfzNbgEgcAEgdAEgdHUceM0geNFozAFozHV4oC10oBlszAFtISF1/f0huf1luf113d0Rqe2xGHW5IHW5GM25GRn9/XX9uSHtqRG5/WXd3XWZ3d3d3Zm6AbmaIiIBAFYBbM4iIZgb/QIBwSCwaj8ikcslsOp/QqHRKrVqrh2tyou16v+CwWNoYEyHmtHrNbq/R7rh8Tgc44qy6fs+3jvqAgYJ8NXMmg4iJikkCAQAlAVlQcIuVlmB/UxQDQ5SXn6CVCEMgUZmhqKlKHVMlQzUEUnmqtLU9VBZEZVAntb60ElMLQ5JRwb9gxch9Ac27USjL0pbHUbNV1dNLExwCnkOntNzeXrdSw1bRuEq5RCDNDFYXSe1CMPBEJfFI4U7vAfuozEsyUEgMfEP0hcnWBCG2KcqOwLpWyoqPiEVqFHhRJOAZACGaAQTQz8kzKhgzbux45FuTknvURam3JAGpk1JoJrE5BMYR/51OYFasAhSJAiI+jRTswtBN0yWunCQFMJSKyyNThQSEZCCJIzJVojbJCmBrgK5TYJqbI1NIIyGRjlAwcnbISCE8QeAE8BZSSiFzi9SFu48nABge/RzRa+QtgLhIAhMZ/DigYcRrnrJhuOkD1SMpfZIFMMFz1SKchFy9iKTMydJD9k1AG2YvgM6fkYQ+bAS2ViGzpUASKdK2nLYAfIwScvrwXwFHuFC1vTw3aCTQi0g/nDhKCuLFSR1RLl439ug9uy+sw9CzkFhG/gJwT2QCmuaPiBC4hvRvc/uxrWEbffBdhwR9QwD4Wxdq1YFcPSWUEYIyf2mA3nRGQLjLBF8Rg/+EBjhthxmDi+2lIXABeFLhXiKqB4Zmmb2S0F+SfTSMDDIydwQ6AEREEwX8JQdAIULkUYNhZQmY0YxCzCBXSwDc+AqSLi4IQkDqwaQHcuGBk8Q9u4RUxC6MIdUlEYckJFiYKQ7xzGhVkLDYEWcOkaYQKVByEJtj9rQZe0OI8ESQSNSDnxIqFFEjPSypgZOgYiyVZBprjXHlEW3xWERJBTCxHYZEaNpEp0p8yp0aZQ4hKhOkllrEiGnAeAWHSQQz3BeShtShQ0T4QNCvk92VBj7fdWiEcUtIymst6iF3BCRVhnFPM9rYRW0osl4BpxDZVustG5U25ohfUzT77bl7PLByRGoAXKXEtgBEgO68g1R32nDg4aTenfT2q8YGSYgFwH5RwOvvwXWcKIV6GCDscBg4IsGjfEoIPISvD2fsBStGTBsAsqU2Q5vGJPsCcMkoT7HXql3wm/LLYwkmrBcYw2xzExaPAfLNPAtRAsVWmNqzNkEAADs=)
=
![](data:image/gif;base64,R0lGODlhgAAYAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAEABAB8ABEAhQAAAAAAAB0AAB4AHgAAHR4eAB0AHQAAMx0AMgAdMgAdSAAcSB0dSAAzWgAzWx1GbDMAADIAHTMAHTMAMzIAMjMeRzQ0HTMzWzNGRjNZfzNbgEgcAEgdAEgdHUceM0geNFozAFszAFozHVtISF1/f113d0Rqe0huf1luf2xGHW5GM39ZM25GRn9/XXd3XW5/WX9uSHtqRHd3ZmZ3d2aIiIBbM4iIZgECAwECAwECAwECAwECAwECAwECAwECAwECAwb/QIBwSCwaj8ikcslsOp/QqFQIwQge06z2CAEIhJtAYPtMiYsgbXi8nSTdRPGiqABcAJvG9rAcGOdGWFF5ZHxKfkWAQhVEG2RSKUUZABRTjluVTAiJQzVFhFmCS5FEiiABBEseSKBTaU56QimKAKhDl0UCARq1hkYRRagnADUBdUKbso+3R7q8Ab5Hw0LFqUJsADCcQndFsUURBby4RdGyDaREELxCgBDWqqzfROFgSeZCeg5FXUPu8PaMeCIiigg+L1yGpGMipuGZRkcGDimo8OAVIxBE0fo0T8grIQaOpDhIbkhGf1FWHWmFJCQSkgllbYRoJBOAjxyiHbQQE8BCnjIlhdj8CCGAqBr4VADoCGAdSnlJQERTKQTYEQZGkrVLCbUI1pvmbAKw2knIVyJaAcxkZqThko9m9l3zpnBZwGAPi4goIgobB6N1SyVhCaBDEqpCJDQRq9YuYcNPFDMRO2twkRhRECXpF3hZScxK2A2BMcCEEqeCk4ipEyKvEcRD4ByRfc2Y3b+2W9s+wpQJbTO7ybQ+Zrc4Q9fGhQQBADs=)
(все биномиальные коэффициенты делятся на
р). Так как
![](data:image/gif;base64,R0lGODlhYQAYAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAIABABdABAAhQAAAAAAAB0AAB0AHQAAHR0dAAAAMx0AMgAdMgAcSB0dSAAzWh1GbDMAADIAHTIAMjMAMzMeRzMzWzNGRjNbgEgcAEgdHVozAF1/f113d0huf0Rublluf2xGHX9/XW5/WXtqRH9uSHd3XXd3ZmZ3d2aIiIBbM4iIZgECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwb/QIBwSCwaj8ikcslsNhsAgXNKrVqVlwRAcl0+ukXp9OuMAExgpMmQFpoCgeqASm4T63Yx9dAMEDR2RQyBQnpUC0QVcERcgYoBFAAORARCAYiKiEKPWkMXcHCRRgJxn2xEfIWDHUMNf0mfoKCaQyECq2enUX6WlQC+AINCnQDEcUgOBZEVRVAADcKERNBFulFDenMA1mLahUkIQxXRz4PWU7Gyl9VFHdzY8O7TAPLwSKIA3kJQrNJGtEPeFRIl5tg+IcCuHalzwUiDSLqIMUknC+C2IcQAfduo8OKwfboM1fJ0DkCqR+QIofTUahGpOKR8cZqm7gioI/38TZmks4iFD57S9PVUkMQZ0DFAYzUJAgA7)
(малая теорема Ферма) то
![](data:image/gif;base64,R0lGODlhzAAaAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAIABADHABIAhQAAAAAAAB0AHR4AHh0AAAAAHR4eAAAAMx0AMgAdMx0dSAAdSAAcSB0dSQAzWh0zWx0zWgAzWx1GbB1IbjQdHTIAHTMAHTMAADMAMzIAMjMeRzQ0HTMzWzNZfzNbgEgcAEgdAEgdHUceM0geNEczHlozHVozAFszAFszM0YzRkZGM0huW1l/bl1/f113d0Rqe0huf1luf2xGHW5IHX9ZM25GM39uSHd3XX9/XXtqRHd3ZmZ3d2aIiIBbM4iIZgECAwb/QIBwSCwaj8ikcslsOp/QqHRKrToFqoDDyjUeAJ+lABDoms8ArBZNJQkV7K6bs4QA4PH8030XfgJlUBhPMoBFNkNbVH+BZhQAPUOFjW+QelKAC1GADEOIQhF+ik9fSwNGnUYVVh+jXZFIqUQWl1CtVDKyQ7R+URlTMkUmhqx6F0XBRIAeSyJozkiuUbLDlLdOJoRFuhpm17VCst1N0GblRWG44kbpRQQBHWSlQjBFAQX1PQGaQgiSngQKeDvCKIk+gUIoHUkGIGA9Jue4RCQiLWEAZko62Qh4pCKACgaYtZtXxAHDIRcwAtDVBJBLYkS+CSHwZEsoJizB2ZJGQAKA/xlLcilpRwTWEJ8ySBKhaeSYkJNoiAJw6qRnE6hKTrx0eTOK1q0BugpxdcGnk5wxK2YbMkaI0iFShZQdgpaLzLdDn9TVOWRiLyJ4kQhNEhfALyFrIQXecIQq1iVft4oFU/JJDQAejTyG+CzJqM1kjuwFkxmACZKrkOAh4o9unm9Jn/JDAmv1ktF8CbuaN3tLCWSjC7s8YhZAoa4Ku4IuRgQEzB6lRjVyXlzwlBFJZmtPgj2avQDFGVZfOVRaCCW8mAwignuKzCMp+Fhpn5tdlcFIpOZYYmPAiyVUPaVHYUQgwsx4UCxXn2dBHbXNEpkA8JV6Sqw3RIRxOLdPEj79RhkFhgs6oeESvimzYYgoKoGCXLOl6KI9UQQBADs=)
=
![](data:image/gif;base64,R0lGODlhlwAZAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAIABQCSABAAhQAAAAAAAB0AHR0AAAAAHR0dAB0AMgAAMwAdMgAcSB0dSAAzWh0zWh1GbDMAADIAHTIAMjMAMzMeRzQ0HTMzWzNGRjNGbjNbgEgdHUgcAEceM1ozAEg0AFozHUgzM1szM0ZGRll/WV1/f113d0huf1luf2xGHW5GM39uSH9/XW5/WWZ3d2aIiIBbM4BuboiIZgECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwb/QIBwSCwahwaAQ+ioDBrHqHRKrVqvWKQSmsV6ABTApksum89TECA0hKCNmCP3Ta9fD9Z4UWBvFS8AbnaDhGdQH0VJgw4JHAEEVBp1koWGVohKCUULRBkBAVItj0OglYSfgHYDAYABeAAPRaKQQqVSKIoAA0NzUZycRQ60kZNTT1cbn8qfwEYPBUIZQq9Gv1ZLSlnHZMvKZd2fRg69g35EUNREKNtV4wDpVdJolG/0RvCmAHwm+NFY2M2qnAAQMN8ZE0dMBCAnJBm4gkIEiRnSbyDEKA4u8BNiQlMVBfOKRaHm0Q5IMdRivVHkyZaQJNgA2PLE8E3Jm98WDgFk7ow3OiJjiMzUOQUhlS9hDCotpOeISjMSo8TpuXQpzzMoqPApk3EK1apgAXQw47DkkahXIvwLuzRZTbZVggAAOw==)
.
Теорема 2. Пусть
![](data:image/gif;base64,R0lGODlhJAAVAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAIAAgAeAA8AhQAAAAAAAB0AHR0AAAAAHR4eAB4AHgAAMx0AMgAdMgAdSB0dSAAzWh1GbDIAHTMAADIAMjMAMzQ0HTNbgEgcAEgdAEgdHVozAF1/f113d0huf1luf2xGHW5GM3d3XX9/XX9uSHtqRGZ3d2aIiIBbM4iIZgECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwZ9QIBwSCwaj8gkRJlEkg5NgEATJS6riOqwoeUUBwHAJQAVOowBwjAszBYLW8ATyQDUh48JMTGkDMtGA1xED0QXQyBTAByARX5FD4MAV2J3AI1DHXaQRAt/USRHIEQcAaaWQodEbAAVAZKoVEhnVZQAnk0GUYVrAQpREUnBQ0EAOw==)
- полином в
![](data:image/gif;base64,R0lGODlhLAAZAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAIABAAmABIAhQAAAAAAAAAAHR0AHR0AAB4AHgAAMx0AMgAdSAAcSB0dSAAzWh1GbDMAADIAHTIAMjMAMzMeRzQ0HTMzWzNGRjNGbjNZfzNbgEgcAEgdAFozAEhZf11/f113d0huf2xGHW5GM3d3XX9/XX9uSHtqRG5/WWZ3d2aIiIBbM4iIZgECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwaZQIBwSCwaj8iiJsBsGpLDR1IKBWgEVcATOjBuhp/ApUqtHpIERlWTHS6OjXe7GMACUAEEYHTEJNpbRR8LH0UNRoFQH4lEBEYNakN2gEgYj0QBRRVJKIxDEo9jAI5EXVAOR2oKRWcADU1NhqNFkQBhcgCZQoVzAHoTRKhZZVkRd0YFHlANor3EQxBJ0b25AsrU2MDY2w2T20RBADs=)
. Тогда
![](data:image/gif;base64,R0lGODlhQAAVAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAIAAgA7AA8AhQAAAAAAAB0AHR0AAAAAHR4eAB4AHgAAMx0AMgAdMgAcSAAdSB0dSAAzWh1GbDMAADIAHTIAMjMAMzMeRzQ0HTNbgEgcAEgdAEgdHVozAEZGbl1/f113d0huf1luf2xGHW5GM3d3XX9/XX9uSHtqRGZ3d2aIiIBbM4iIZgECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwa3QIBwSCwaj8ikcln8HIgRZZS5DASow8bwuRR0sEfuo0K1DKdMBLhoHirWGfBnPRx5hwLi4JoJcAEaQhBGAQRDAQtDanQAfwAPRgVDDkWOQ3NzRWNFVp1WRSeOkEQJQ22XlkMDR6N0jqtDcUJ2X0SpQ2SalGu0eFCxWpVIFKxFfZ5WwaaXb0MMW0eDRpTPIHWMbkKbQh+dytOXAcEXV0TfdJ9FtUoQ61LYSs9UBkyt8ISI90QS+kdBADs=)
в том и только в том случае, когда p(x) eсть р-ая степень некоторого полинома
![](data:image/gif;base64,R0lGODlhWAAZAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAIABABTABIAhQAAAAAAAB0AHQAAHR0AAB4AHgAAMx0AMgAdSAAcSB0dSB00NAAzWh1GbDMAADIAHTIAMjMAMzMeRzQ0HTMzWzNGRjNGbjNZfzNbgEgcAEgdHUgdAFozAEYzRkhZf11/f113d0huf0Rqe2xGHW5GM3d3XX9/XX9uSHtqRG5/WWZ3d2aIiIBbM4iIZgECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwb/QIBwSCwaj8ikcslsFiFJqBPJCVivhqk2mVUKtkrOoNlNfpvS5QE89AxHAQzbeGpypgwkAbskNOZHI0UOAX9yQiFFAQOJLAEISSxaDnlMD4pjAI6QQmtCBENlZUSCI5VCDoAAGQlOo0KmgoNCGUOSsK9DoIN/RIRXAbmhU8K7syxltcNHGYdDqXOZTSPCSNCn0shIE0YOzkIaTQFFFkvC3N0AHJULCkSXRn/uJEOeRdW6RWdK8ETyAPTqfQqQp9cQg3BOjYOVBNirX8C6VfAz5A4sgkMWDjkFzkg/JWlUHeHA6R2aJicKLPEmkolBISqVQHtmheOQCElwtlwS8mbOEJ1AwywKSrSo0aNbHEhTFQQAOw==)
.
Доказательство:
![](data:image/gif;base64,R0lGODlhtAAYAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAIAAgCvABIAhQAAAAAAAB0AAB0AHR4AHgAAHR4eAAAAMx0AMgAdMgAdSAAcSB0dSB00NAAzWgAzWx1GXx1GbDMAADIAHTMAHTIAMjMAMzMeRzQ0HTMzWzNGRjNZfzNbgEgdAEgcAEgdHUceM1ozAFszAEZGbl1/f113d0huf0Rqe1l/blluf0RubmxGHW5IHW5GM39/XXd3XW5/WX9uSHtqRGZ3d26AbmaIiIBbM4iIZgECAwECAwECAwECAwECAwECAwECAwECAwb/QIBwSCwaj8ikcslsOp/QqHRKrVqvzM4By+16v+AnKEwum89DCUCAbitX22FFOSd7AgGF05KsD/ELRCF6GUdjTHBEfEmLVngbTw5DcUoDJmSSTpRIBEUrRRcANn94UZkAm5wnVXESkEweck4IYbFOfkq0RIFFuESHS7YAvkm6UsIAvE4hT59hp0rMTqfOfwWXRiJ5T9JN1VAxlkMDRAIBACEBlCNCE0YBBX96QsZT5ujqAB7QQhIBEUTcEYH3h0g9ZYWi+EM3hB0AgQPjCQmgrN6TTWqKGBgCkEgqIZ++9eNQJB2ekwH4EdkoBAIAfmyEUPr4siaRjACqSbj2JIYA/4CJitAMaUQCSSLaUOI5ZQNjkQRDkOWkueYITipQhcSSum9IpqBFfhbtmIxKVyH8wIa1OmVTTCHdwmGblOToTbJS4g5QYVPUJrs0pfYbIhIKJcGo6o6NInccET8hVFLFwLak0qVHIEs6i+6URL9GWvRNs2tK5CGfPSKhXDTb5ZREOhBWBoABXSMQiQC0LVpIjCu2ZXod0q1BkdyiihGuImlU8ONHdgPoDeA3FV5GCZ9UyVF7pg7niHB3smJ71LCw8YYgGx4AeLIroNGGYs5B4e4gYbtvj7ZKqSJzJTFBgH1cQWB/RnxwxCpQ3CfFgUJQwOASxADnRCdLXDXFc0Rw9ijYERgmkV1pVlQ4RIgigoHHPFc0QsWKR8DYz39VlMefFP7oN4WLXAQBADs=)
. Обратно, если
![](data:image/gif;base64,R0lGODlhQAAVAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAIAAgA7AA8AhQAAAAAAAB4AHh0AHR0AAAAAHR4eAAAAMx0AMgAdMgAcSAAdSB0dSAAzWgAzWx1GbDMAADIAHTMAHTMAMzIAMjMeRzQ0HTNZfzNbgEgcAEgdAEgdHVozAFszAEZGbl1/f113d0Rqe0huf1luf2xGHW5GM3d3XX9/XX9uSHtqRGZ3d2aIiIBbM4iIZgECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwa9QIBwSCwaj8ikclkkHYgTZZS5DASow8bwuRSEsEcuBEPNDClYBLhoHirWHDBpPUQNRMMBkXDlBLgAHkIRRgEFQwELQ2p0AIAAEEYGQw9Fj0Nzc0VjRVaeVkUsj5FECUNtmJdDBEekdI+sQ3FCdnhEqkNkm5VrtXlEaEIcDka4ABatRR2fnsREqCRvQwxbR4RGldQldY1uQpxCJM1JvADizhpXRM7doEW2ShJfTMHdSNRUAkyu9oWJ/VAAHgkCADs=)
, то
![](data:image/gif;base64,R0lGODlhwAAbAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAIAAgC7ABYAhQAAAAAAAB0AAAAAHR4AHh4eAB0AHQAAMx0AMgAdMwAdMgAdSB0dSAAzWwAzWh0zWh1GbDMAADIAHSwAADMAHTMAMzIAMjMeRzQ0HTMzWzNGRjNZfzNGbjNbgEgdAEgcAEgdHUceM0geNFozAFszAFozHVszM0YzRl1dM0hIW1tbW0huW0huf11/f113d0Rqe0Rublluf2xGHW5IHW5GM39ZSH9/XW5/WXd3XX9uSHtqRGZ3d3d3ZmaIiIBbM4iIZgb/QIBwSCwaj8ikcslsOp/QqHRKrVqv2Kz26dl6v+CweEwuSyMAgXltAgwAaPV67h0tABn62o5/VpJ/emYXAD6CYnIAhIZOB0sEh2aBkVs0ACdEk0sWTQiCIWMBAyxroGYNAKKkTCNPDpRfeUymWLRlskUCARupjkmiQj4BdzlXHwEBT7ZHyB1Jwm9CyROjdMtGzU3AhcNDEdVGEgVCH0O+RTIOMkVo2MjvyUaJEE7XQwL060yvqFD2X/gAzHiSTl8THwqI5DuXy0gEemeekID3rp+Qh09yBHRCEdmUiR0twoEYJVGTEc6EGDCHpBy7KT4YYpHJxGWUf1L+0XRiswknxSGtgu0EgMFhyiEgKYoE8ArbEnsGnVhqGglqEpJIij5hAJShhCP0uBLxJEWGLxl3ADwAUEKJziFpmYj1V+ZcXCZhn7wDO0RGAIvxAESN4sGjEINYi4j4FSBxnCGBCyem0kVIZQCXjSxGgiwxigErImgIOOMv5CYglFDwCcsJH1ytqaQYwocMgRdKIhzFgnjLothWNCae3ATk3SOaiiTPsrbtl+XArUCPXiWwFlXUp7QhAWDEtuzghcAOT778lG+rzEP5diUIADs=)
. Тогда
![](data:image/gif;base64,R0lGODlhFAEbAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAIAAgAPARYAhgAAAAAAAB0AAAAAHR0AHQAAMx0AMgAcSB0dSAAdSB00NAAzWgAzWx0zWh1GbDMAADIAHTIAMjMAMzMeRzQeSDQ0HTMzWzNGRjNZfzNGbjNbgEgcAEgdAEgdHUceM0geNFozHVozAFszAFszM0YzRl1dM1tbW1tISEhIW11dbllZf0huW11/f0huf113d0RubkRqe2xGHW5IHW5GM25dXW5GRn9ZSH9ZWX9/XW5/WX9uSHd3XWZ3d3d3Zm6AbmaIiIBbM4iIZgECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwf/gACCg4SFhoeIiYqLjI2Oj5CRkpOUlZaXmJmVBZqdiBycgzSUDwGep5KghKOpqK6vsI8enRGxtoazt7qnuQA2hA8XAg67kS2DDwACxsXNx4LJy4wjAAPNt72FIQfXi9mE2wAW3eS4iOHjnrWI65cbAaaQ8NyCvSqHxJLzlTHwjRMAgDwSWE7QPkky/DGiELCRtEahEhHAtGHBpBj0GLWDtKFTxm+FNi6yWLAipo+KJDCaAYBEI5GIDLirlDGetgDWFIEcRPJSjEEiAnBDUQjns0X94GlItFNSUwA9Kf0UFHRo0QFHGUU9FOLR1kgmJ2V0FfbkonQFmSLqaFYRWlIB/4gtFZQVgNGAQhPZZMS20Lu9h8YaepDTW6KtfyNNTUS4rsGcQPI6egrp6VYOChstRtT4EE5BkQULehgxIqGfMaImOwevNbyoZUcPyncIY6amfWULou1I9KPUmyfHiv2Q9yLfjoAn6ksQQAzThB4iM86x0OpGyBuFcN16a8/rkoJLkr4oKPcAX8ufR1/o+8VL5AkBiZgb+qANc5FdimofkW1YZfX3SHaN5HYNboPMRwmBjHCgSE+FKXhIBYPlZ8h6frXnWWC3HcbTIaVQV4h4kVDoVIeI9JSeg4qQCImJXJGkAAKEQIAPADSyJIhMlZT1nCD/NQAACCMyOBOQofxXg9MgMBliZCLE0JiWIWH96FwCkDyJSJSJCMCecbT105NNJAKmiIGJATlbIVoaluIgmJk5pH7kuYgUewZF8sEhLALQZ5+G7PmmIHEWQo010Yw4SUJjLtKBITZq5E562A1HqSLcvAVAm1M+YiAjmbJJjg4TKfKAhZN8quhuosZyKSH5AdScmp2i8qoygzA0q3O2lIJnSIk0Kclf2QlJJJAHvRIngV9tlGytmSyriEuDqDTIs9BeI2enrV2LVbadWnQXuOSWO4im5pKDbrrspkVYu+W8e00gADs=)
.
Таким образом получен следующий алгоритм PSQFFF разложения на свободные от квадратов множители над конечным полем (Polynomial Square-free Factorization over a Finite Field) :
Вход:
![](data:image/gif;base64,R0lGODlhJAAVAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAIAAgAeAA8AhQAAAAAAAB0AHR0AAAAAHR4eAB4AHgAAMx0AMgAdMgAdSB0dSAAzWh1GbDIAHTMAADIAMjMAMzQ0HTNbgEgcAEgdAEgdHVozAF1/f113d0huf1luf2xGHW5GM3d3XX9/XX9uSHtqRGZ3d2aIiIBbM4iIZgECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwZ9QIBwSCwaj8gkRJlEkg5NgEATJS6riOqwoeUUBwHAJQAVOowBwjAszBYLW8ATyQDUh48JMTGkDMtGA1xED0QXQyBTAByARX5FD4MAV2J3AI1DHXaQRAt/USRHIEQcAaaWQodEbAAVAZKoVEhnVZQAnk0GUYVrAQpREUnBQ0EAOw==)
- нормированный полином из
![](data:image/gif;base64,R0lGODlhKQAZAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAIABAAlABIAhQAAAAAAAAAAHR0AAB0AHQAAMwAcSB0dSAAzWh1GbDMAADIAMjMeRzQ0HTMzWzNGRjNGbjNbgEgcAFozAEhZf11/f0huf2xGHW5GM39/XX9uSHtqRG5/WXd3XWZ3d2aIiIBbM4iIZgECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwaZQIBwSCwaj0jiJMBsFpASZlLINCQngqQEMR1erEOKNxDRdolg4yAx3Z6FaaKC2y4GBBYAKJCOCyV+R25EFwAXdEJfRk9nEkcDR35Zb4NEEmVFcQFFEGZGDZFDkEQEbYhCbAcAGF5gCk1NRQoAowCOiQGIm2hvcAAOf6dTgUgMekO3b8RJC8hVSRfPb3d5vdZDwNfaAAqT20RBADs=)
, не являющийся константой, p>0 – простое число.
Выход:
![](data:image/gif;base64,R0lGODlhXQAYAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAIABABXABAAhQAAAAAAAB0AHR4AHgAAHR0AAAAAMx0AMgAdSAAcSB0dSAAzWh1GbDMAADIAHTIAMjMAMzQ0HTMzWzNZfzNbgEgcAEgdAEgdHUceM1ozAEgzM1szM1tISEZGRll/WV1/f113d0huf0Rqe2xGHW5GM39ZSHd3XX9/XX9uSGZ3d2aIiIBbM4BuboiIZgECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwb3QIBwSCwaj8ikcslsOpOPp3RKRRqYgqp2eFUOtssDeIxESTOM54LsRDdH62EjEDg6iqsAYVgXmtlzAWlId0R5e0J9AGJDcUYrXUZrjkINbJRHkEiTRJZDjEeRRQWDnaVaf0uiRKRFnkMJRyOrQxVHr2OxSbNItq5pHENpFqK0ACQAmAANFGwZqkfImJ6+z0IYRIWGQgpGoFq+yUraQyvcRYyBxgDWfEMWgkMjQwVdFu/4QvVydKseDaXaJXoXT4iyIdiyOYnCxkgHO00YPvmyhJmcJ7iSNDsFgGKSjEYSFoGghGTDI2k2HDG5ckmGAAhOklG5LKaWIAA7)
и
е, такие что
![](data:image/gif;base64,R0lGODlheQAkAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAIAAwB0AB4AhQAAAAAAAB0AHQAAHR0AAB0dAAAAMx0AMgAdMgAdPQAcSB0dSAAzWh0zWh1GXx1GbDMAADIAHT0dADIAMjMeRzQ0HTMzWzNGbjNbgEgcAEgdHUceM1ozAE4zAFszM0YzRltISF1/f0huf1luf2xGHW5GM25bNX9/XX9uSGZ3d2aIiIBbM4iIZgECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwb/QIBwSCwaj8ikcslsOpOfp3RKrVqv2CkpwO16v91slqOQTpJnMReT5D6KGe40faQLuWXhSmpYCsQQAUoBA0YZDFN9Sn9EJHlzTQdZgWxIhIaQTJJEjxZOHE+IV4GDhXCiTaBOqI5DAW9DBAFsAYoAESJFhLkrAWUom1aUbQO5RBlGga9HxgC9pgCCQihFj0cRBULIQraNQqgAEEYcYAHgQ6TEhufnRN1DiOfiQq1Ie0RvJO+xybBVw5agDdnWRJ8RFAT8ofNnbdGQfdqSYUkXcJ2Rhg+PECQyD0C9OkNUOYMIoEKySiHLtQs3i1iziOOOrNhXAkA7CCgxDlkghEO3xghH3vCsKSTYP2kVTw3suRKok2AfjYQx4m8LKqQkJrVMeowjF1sihfhDGqdqNSQalDhdYudoKYtP1iqxE3UINSUoBLw8qRWl1GJwlngokndvEZxni5DzxRaNGJZv4eAx45jI5MeYD289cmkK0sygH8sa9Dm06dNSv5wDoxC169ewY8ueTbu27duvwe7zibs3FQJHgPsezmQDgLDHAXTgTLy5EOMeBdIT2MC5c+jwAAwmgogcSevgj/gNX1uQhC5lBMWZbLV5EAA7)
- разложение полинома
![](data:image/gif;base64,R0lGODlhJAAVAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAIAAgAeAA8AhQAAAAAAAB0AHR0AAAAAHR4eAB4AHgAAMx0AMgAdMgAdSB0dSAAzWh1GbDIAHTMAADIAMjMAMzQ0HTNbgEgcAEgdAEgdHVozAF1/f113d0huf1luf2xGHW5GM3d3XX9/XX9uSHtqRGZ3d2aIiIBbM4iIZgECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwZ9QIBwSCwaj8gkRJlEkg5NgEATJS6riOqwoeUUBwHAJQAVOowBwjAszBYLW8ATyQDUh48JMTGkDMtGA1xED0QXQyBTAByARX5FD4MAV2J3AI1DHXaQRAt/USRHIEQcAaaWQodEbAAVAZKoVEhnVZQAnk0GUYVrAQpREUnBQ0EAOw==)
на свободные от квадратов множители.
Реализация:
BEGIN
k:=0; m:=1; e:=0 // инициализировали
label3:
j:=1;
![](data:image/gif;base64,R0lGODlhqQAVAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAMAAgCiAA8AhQAAAAAAAB4AHgAAHR0AAB4eAB0AHQAAMx0AMgAdMgAcSAAdSB0dSAAzMx00NAAzWgAzWx0zWh1GbDMAADIAHTMAHTMAMzIAMjMeRzQ0HTNdXTNZfzNbgEgcAEgdAEgdHVszAFozAEhOM0ZGbl1/f113d0Rqe0huf1luf2xGHW5IHX9ZM25bNW5GM39ZSHd3XX9/XX9uSHtqRGZ3d2aIiIBbM4iIZgECAwECAwECAwECAwECAwECAwECAwECAwECAwb/QIBwSCwaj8ikcslsOp/QqBRgUV6mR1BgKwFot8TQNkD8jh/I6lN9ZGMPRLfRLUfClwITtpganIZ9RGRCNQEcgHcAEwpFNYlNj0cCex1DjkyTQ3lWTgh7YWhEoQCDQyGMQ6OkRVdPrUueU5VCr7BEsUchTymfQxNFv0LBRYnDwkVdTrpOqk8YQ8lNo7xCBHCFABRGAQNDAQtDuEKlTpdEid1FIYmRHaPaRgQBG6SJ8ITc3uBC4vHz9Ubu4UtHah8AceJYAKgAIJIQXtSITDhkxMyYABCOXNwyCpXEjsAsORRCocChWQ2PoMkocUnJk41GAlgZ0hdFB4iQEDhiTFZN/wA7tw1BOYRANJkJhnZJMdKokQnRjiQV0iFqyiNOgUULtmyITAAUJVqFEsPAH0J+AMTIOnRI2bNecx4JayCuEaK+ltDlIxPvMV9dal01koFnko1gjHgU4nGCqkBDFq86d+RViFEjMzRTFNaI5c0yNT8NG6yZQGgAGABo4bZXz56lQhBUVITcELhG1hE5XUPt7XBNdB/BDaB3jN/8Wns5Ei0FRiEebDezrWQMyzG1E3vbaLCMxi0siUR7DiB686IOrSMBUTuUeUBFwhupoIeJ4F74jzAk8kEJ/SguFNEfE/tFUUcRmSjRU34MIghFgkgYM4F8DzIhIX4HNqghFV5otwphh9QlkWEbRAQBADs=)
;
![](data:image/gif;base64,R0lGODlhUwAsAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAIAAwBOACYAhQAAAAAAAB4AHh0AAAAAHR4eAB0AHQAAMx0AMgAdMgAdSB0dSAAcSAAzMx00NAAzWgAzWx0zWh1GbDIAHTMAADMAHTMAMzIAMjQ0HTNdXTNGbjNbgEgcAEgdAEgdHUceM1ozAFszAEhOM11/f113d0Rqe0huf1luf1V7amxGHW5GM25bNXd3XX9/XX9uSHtqRGZ3d2aIiIBbM4iIZgECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwb/QIBwSCwaj8ikcslsOp/QoSVKrVqFB6bgyrVemq6u+AmCPsZowCAAAAWyQlMxQJDLAoohIo2eFIQcEgBwRSkAKRBFFHxjCUMch4RFA0eLjFxlQwZYSBwbRhSCl2NnMpJEGJWjVwtCIIQTR4KtKkR7SlOrRikBvYlEoocBvwBsRGdJp0dbukMVTl9FL0PRzUWtSC7MSpZFm21PhmK9eUm5SOdDIb0BGQByRHR2eHpz1mRDykIP4kTdR+wC3iMiJ4U+NaoGUmGQr1OlYFQCSpxIsWIvAJCEmEKSClSSdROJNdvzQUgsI7OM3FL4RN6QYLyIGRuCbMhMlk2eNamGs4o2dXhJ/vW0ks5IUV1HifAcSmXjkm1MoyxNsjLqE4hLalo1MgAOm5PxCNgsB6Dq1msAGgAQcfCMSABCzwpJ4SBCwyMDsMLVK5esQYce5RZZqq+WViFxz8poshiJWbkhjGSyOaRDAJiHBR/RqRkNVCQUPnVmknRJEAA7)
IF
![](data:image/gif;base64,R0lGODlhNAAVAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAIAAgAwAA8AhQAAAAAAAB4AHh0AHQAAHR0AAAAAMx0AMgAcSAAdSB0dSAAzWgAzWx1GbDMAADIAHTMAHTMAMzIAMjQ0HTNdXTNGbjNbgEgcAEgdAEceM1ozAFszAF1/f113d0Rqe0huf1V7amxGHW5GM3d3XX9/XX9uSHtqRHd3ZmZ3d2aIiIBbM4iIZgECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwaRQIBwSCwaj8ikUhhRSpbQCyKpMkAF0KQjMEU+s4csMtQdDoYNMWChNpYBgTjgUVQFCMNAYhhuD8lFaVVIbAxFDkUbcYtxhm5EdEJWRwVph5Z+gEIhf5NGF0eIfkNloEOeRRNsh0aMi0eaAGEZQx91ACW1fKOkeXhCGkUBjhgBmJy8W3dIELzOSVhLos9QTdRqQQA7)
THEN GOTO label1
label2:
e1:=j*m; IF e1>e THEN FOR i:=e to e1-2 do
![](data:image/gif;base64,R0lGODlhaAAYAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAIABABjABAAhQAAAAAAAB4AHgAAHR0AAAAAMx0AMgAdSAAcSB0dSAAzWgAzWx1GbDMAADIAHTMAHTMAMzIAMjQ0HTIyWjNZfzNbgEgcAEgdAEceM1ozAFszAFozHVszM0YzRltISFlGRl1/f113d0Rqe0huf1l/bmxGHW5GM39ZM25GRnd3XX9/XX9uSGZ3d3d3ZmaIiIBbM4iIZgECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwb/QIBwSCwaj8ikcslsOp9ESFIKrVqv0MJSgO0WtUqudxhpGsZo5SqdeSrS1QyjWXoPG4FAdVQMDPgvAQcAa114AXNQDn1/AIGDQmdDdllHdSVFDUd5nHlHlFAvYESYAAuZRJJPJaNFBEYNiVWFV61Dr7BFCFW2Qxa5XbtVrEe/sHMeQ7IdR6OiSBKwFUUanZynRm1LeF9H0cDG2k+LSAlFqlDGpk1lQ+REc+YmqUKHrcJFGEWyJQHYAHqElLJib4i4ZEo0DOn3L+CQf0/0EXnADo4VikyoLOEERuKQFQJEKGkwDQ4HABc4DnlxREwSTUomDEGIRaPFJKCiTFkSSBYRDIc3oTik2S9PyStBAAA7)
;
![](data:image/gif;base64,R0lGODlhSQAYAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAIABABEABAAhQAAAAAAAB0AHQAAHR0AAB4AHgAAMx0AMgAcSAAdSB0dSAAzWh0zWh1GbDMAADIAHTIAMjMAMzQ0HTNZfzNGbjNbgEgcAEgdAEceM1ozAFtISF1/f113d0huf1l/bmxGHW5GM3d3XX9/XX9uSHtqRHd3ZmZ3d2aIiIBbM4iIZgECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwa5QIBwSCwaj8ikcslsOp9NBNSJMiwFU6IjIM16v8ku+NhofsAfsXAbAD+KqMBg2BYewGrAYgywHvd7Qw4VRRkBh4gBgUNnRXdjfkUjBGVaeEZ5UB+RRRZGDpVTaUMaQ6FEnEMXnKlCIHpFDkeJiEdingAZUxhEb06PWRlibJx1ALxMukTGFwGhi1BsAx1IDAAUQshG2kK+SxB8SYaRvM2HCUkFS7LhSBkTTdxDEUn07UgfinRHhuj3U0EAOw==)
; e:=e1;
![](data:image/gif;base64,R0lGODlhnQAVAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAIAAgCYAA8AhQAAAAAAAB0AHQAAHR4AHh0AAAAAMx0AMgAcSB0dSAAzMx00NAAzWh0zWh1GbDMAADIAHTMAHTIAMjMAMzMeRzQ0HTMzWzNdXTNGbjNbgEgcAEgdAEceM1ozAF1/f113d0huf0Rqe1V7amxGHW5bNW5GM39ZSH9/XX9uSG5/WXd3XWZ3d2aIiIBbM4iIZgECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwb/QIBwSCwaj8ikcslsOp/Q6FKipEqPnYBWmNU6ht1ABqwtM5DWqlqaPrbbS8MSJbgeRwMiHjQMDFtiQyNyQg8IRS2ESopIdFCJTARDKJJMcEkHdkZnYJwAfkQdh1yen0WXRqhHmUsYQqpGrEKySB1PI5pED0W7hUeKvUPBQl9Ktk64SnXET57JgHmkABBGAdGAowC0plGMkAB4Rh2E30MantREBYSg6UTWQthD22Rb7n3Rn9m0sg/FABYAMBIEzsiDMeLKKCzVR2EAT9mEQeT1ZyCABAAUAOBjsWAyXQiPfClX5AzDYQe5FBmEpMCRYVc0UBTispo5IwX+DRyxoIGg3I4Aas484g5oToP/hh1CMQQogJDC/kmhwyfeAD4ojhKRKYRqEUUsi0QUmARqIakEhYQ1wnUoAH9DxgKtwPBtLYda6o7NBhNAPgBjQTU9ZWRu3b5CNOg8UgLAYV3vGN0b8gVj41yQM/cBc1VYEcFIWhAVeRHA5SWZOCQRjYRe3CId/o14mBi0489PyjS0beadw7EqwWCRTRvABtuc1r3Ld2yzkOOyS9U1UnUK5utMJiOpvmYI9yLam8AiskwJYuzoh1RSsj4JyulE2iNJ6Qv7+PToJ2DWL4V/E/8ABAEAOw==)
;
![](data:image/gif;base64,R0lGODlhXAAsAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAIAAwBXACYAhQAAAAAAAB4AHh0AHQAAHR0AAAAAMx0AMgAdSAAcSB0dSAAzWgAzWx0zWh1GbDIAHTMAADMAHTMAMzIAMjMeRzQ0HTMzWzNGbjNZfzNbgEgcAEgdAEceM1ozAFszAFtISF1/f113d0Rqe0huf1V7amxGHW5GM3d3XX9/XX9uSHtqRGp7VWZ3d3d3ZmaIiIBbM4iIZgECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwb/QIBwSCwaj8ikcslsOp/Q6FCSnEivWKlhKch6v8PL0Mo8gM/SwbDzXKDfzIB8OBq+AoRhAM5vdhxDW0ZuDEUQfYhED0MlgkQpBYCGkol8JQlEjkQaR4eViJQvmkImAG6GGZ98ZhxDi05mYFSqAHd5RJR7QhsBlCVno0ddiRG0QmTGSCnDSRCpXmxOv5WzR9Wdc0x1RHh1dwhDsXrJSqdMwUIL00TORx5y8HKFtOJKjUgFneRQmOdInEYgUIoSr6DBgwgBfBgyMJAddAAq6ENykFy0Ja+OKDBSbx8SCHI06QLQChejAPMAjExXZKVHJA0AiCFZpFgTZC+ddAjgqOSQfGXbmuWMclHJNSNHEyUd06QEynFDlUAcwizqGZxJOlrFUnSJua1xbgGIllGP2ADgAGgF24ySBQDofq0T4oktkw5f7x3JN8luE0wpHCJ5NqSu3yQvMFEQbEQiqsNLeCo6AmhjKSFrIRNJa1KI03m8GGmWEkHEaERVJ57+FAQAOw==)
// вычислили
![](data:image/gif;base64,R0lGODlhKQAYAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAIABQAkAA8AhAAAAAAAAB0AHQAAHR0AAAAAMx0AMgAcSB0dSAAzWh0zWh1GbDMAADIAHTIAMjQ0HTNGbjNbgEgcAEceM1ozAFtISF1/f0huf2xGHW5GM39/XX9uSGZ3d2aIiIBbM4iIZgV+ICCOZGk65oimLFu0ogDPwDobNEvlYkIygUDuUgoMiJ7AAbAp+XKvVAJTYpBwNEzURDAxFqQlbVuSeEWVEdi09ZBJD28EYAbsaI0WooQFBshCIhMlawAYAU8AgYYwCgAQgiV5NDYmFH8jgyQbAkQtDHM6oTCVJaUmh4mLPCUhADs=)
IF
![](data:image/gif;base64,R0lGODlhOQAVAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAIAAgA1AA8AhQAAAAAAAB0AHR4AHgAAHR0AAAAAMx0AMgAcSAAdSB0dSAAzWgAzWx0zWh1GbDMAADIAHTMAHTMAMzIAMjMeRzQ0HTMzWzNbgEgcAEgdAFozAFszAEhIW11/f113d0huf0Rqe2xGHW5GM3d3XX9/XX9uSGp7VXd3ZmZ3d2aIiIBbM4iIZgECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwamQIBwSCwaj8ikUilJToyCJRKDkAIMy0ExYC0+uNKn9EAEd4lVpea8GEbPw9BQFSAMNW2IsS6kJ4RkQm9wQmlCDw5DFldHcnJED0OBQwGVlmZEj3dFIVhHBUaIQhSEQ4aFACVDnkcXXkOkpZqmRaxFFW2QSBuXlgxHpwABtnpGiQoAIpKlRWtFf0QaiUIhAb8AGWYhucKlX3xLIMzjVlpKD67k6utdQQA7)
THEN
BEGIN
![](data:image/gif;base64,R0lGODlhUwAsAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAIAAwBNACYAhQAAAAAAAB4AHh0AAAAAHQAAMx0AMgAdSB0dSAAcSAAzMx00NAAzWgAzWx0zWgA0QB1GbDIAHTMAHTMAADMAMzIAMjMeRzQ0HSw0HTQjIzNbgEgcAEgdAFozAFszAF1/f113d0Rqe0huf2xGHW5bNW5GM3d3XX9/XX9uSGp7VWZ3d2aIiIBbM4iIZgECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwb/QIBwSCwaj8ikcslsOp9QZiVKrSoLTIF1y3UauuBwkSEWD7CsgAYQKaYJw0B5PkQAFBIh9khuFCd0YAtFe0UoAxBGE4mBVh0HRCOFRRtHgI1lk0MlAGR/a5hUnkRtT19MFKFEHkcdRXJCHAGMACNNmkdaoXliU0woqgC6ShOgSa5OI6ONqUnNRGdCsAAirwTVaZBCp3HBTHZ4eke2AH5El0YeAevsAeahtg5DkkgDlt5Qj4RIlYq0VO0CChw4EICvISxwCblwD0lBVSyOlCqSyA6nIdzwMTFGhNYId92ILAMwTWMTXlJMckEhoBoxlWCeHZEZimaRgzCtKCTCMqcVYpxKMvpsgqwJuaFHAsAR0uHBxDhLs2FEigSdOCO2jg4pRpXPEAw77SnqinWIvJ0AOApZRLZIAgAWrhq5MBKA1bZpCj0dUhHAxbZItDH1CBKArDGAl4RoAjSxkWFJ7jqmQjMIADs=)
;
![](data:image/gif;base64,R0lGODlhSwAVAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAIAAgBGAA8AhQAAAAAAAB0AHQAAHR0AAB4AHgAAMx0AMgAdSAAcSB0dSAAzWh0zWh1GbDIAHTMAADIAMjMAMzMeRzQ0HTMzWzNdXTNGbjNbgEgcAEgdAEceM1ozAF1/f113d0huf0Rqe1V7amxGHW5GM3d3XX9/XX9uSHtqRGp7VWZ3d2aIiIBbM4iIZgECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwbfQIBwSCwaj8ikcskEQJTPprQYRVaRKgNTMO1qlwJP8qo8dJvkpJnIFTami7NyMw0RA3iAo6gKDIYBCENrZ35DdHpGhkKBg0RvWUhxcUQPR3iYeUUPb0IUAF9FdnabF0J7QqFFBJ2VrV0blEIhqkQER5YApLq1Qxi4ckMJACVDvUOmm2+/xkgTskO5RBuZmNAAKsMSzUcTwABmGkNiRCrE447BAAGqqEVvCgAiQ8WMf0KIgJQZAa27wYLeDQkRYF+AIteGuFPH0AG5JWmIFGAijeGRiUsqIolgsaMSjkOCAAA7)
; incr(j); GOTO label2
END
IF
![](data:image/gif;base64,R0lGODlhNQAVAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAMAAgAwAA8AhQAAAAAAAB4AHh0AAAAAHQAAMx0AMgAcSAAdSB0dSAAzMx00NAAzWgAzWx0zWx1GbDMAADIAHTMAHTMAMzIAMjQ0HTNdXTNbgEgcAEgdAFozAFszAEhOM11/f113d0Rqe0huf2xGHW5bNW5GM3d3XX9/XX9uSHd3ZmZ3d2aIiIBbM4iIZgECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwaVQIBwSCwaj8ikcjhRNpdKzGFZgAo+0CMkME1SsgAD2BjqHjXj0NhoHlRVAUDEGCAMA4iheC0sF0UAEgBVZABqRRAXRQGMjXFsRAtDIYRGA1p8fWZoRJVGiogPmQBmX51IFZhEG46NDUV+QgxFc0aiCQAjQyajQl0bR6J9Aa8AGY9DxWtbdUkSWFCmvUsCUBDT2EzZQ0EAOw==)
THEN EXIT
label1:
![](data:image/gif;base64,R0lGODlhZAAlAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAIAAgBfAB8AhQAAAAAAAB0AAB4AHgAAHR4eAB0AHQAAMx0AMgAdMgAdSAAcSB0dSAAzMx00NAAzWgAzWx0zWh1GbDMAADIAHTMAHTMAMzIAMjMeRzQ0HTMzWzNGRjNdXTNZfzNbgEgdAEgcAEgdHUceM1szAFozAEhOM11/f113d0Rqe0huf1luf2xGHW5bNW5GM3d3XX9/XX9uSG5/WXtqRHd3ZmZ3d2aIiIBbM4iIZgECAwECAwECAwECAwECAwECAwECAwECAwb/QIBwSCwaj8ikcslsOp/QqNT5OUyv2CxTpO16v+Cw+Mgdm8/lsxqcXruxo4DiTa/b7/i8fs/vTwOAgQF+hIWGh4iJfBZJF14ggHNKjI1FgAtFExsCTjZWSgMoWiBNn6CiRJhEJFCOTAijD0uur0QrqkYSTbpMK6NLrE6+qUUdAJRCAoMkAaYURgEEQ4NCsJa8TCCyQwJWNoPPltJCckPWALer0UcFQ7qeSLIQRBMeSYKBRaRGLAAVAKZsoTNSbwguJQmG7AOIRAA2IROyaCviYMiKgEQ4EbSIa8K4IsEAwDCQAh1GhQQfRlkoJKSQk0PsZcJ2EAktEtsYGmkBICfEcyRx8AWYp9AnrZdIMhyJKCTdEgZDYBKxcQTGLyI+AYQrogsqTyFWiSlZEYjoEJcAqAH4EABb1rQqk0wUMuIINrJE2RbJ6VRJSST/mBydwhIwqllFahqBCmoJU4lvjQxg8ripYiKRliAzshkLW7VXOmdGEgQAOw==)
; inkr(k); m:=m*p; GOTO label3;
END
Вычисление числа неприводимых полиномов над конечным полем. Согласно ранее доказанным фактам в
![](data:image/gif;base64,R0lGODlhKQAZAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAIABAAlABIAhQAAAAAAAAAAHR0AAB0AHQAAMwAcSB0dSAAzWh1GbDMAADIAMjMeRzQ0HTMzWzNGRjNGbjNbgEgcAFozAEhZf11/f0huf2xGHW5GM39/XX9uSHtqRG5/WXd3XWZ3d2aIiIBbM4iIZgECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwaZQIBwSCwaj0jiJMBsFpASZlLINCQngqQEMR1erEOKNxDRdolg4yAx3Z6FaaKC2y4GBBYAKJCOCyV+R25EFwAXdEJfRk9nEkcDR35Zb4NEEmVFcQFFEGZGDZFDkEQEbYhCbAcAGF5gCk1NRQoAowCOiQGIm2hvcAAOf6dTgUgMekO3b8RJC8hVSRfPb3d5vdZDwNfaAAqT20RBADs=)
найдётся неприводимый полином степени n для любого n. Также
![](data:image/gif;base64,R0lGODlhMwAYAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAIABQAvAA8AhQAAAAAAAB0AHQAAHR0AAB0AMgAdSB0dSAAzWgAzWx1GbDIAMjMAMzQ0HTNGRjNbgEgdHUgcAEgdAFozAFszAE9HHEZGRk5GRkhuf113d11/f2xGHX9ZM25GM39/XX9uSG5/WXd3XWZ3d2aIiIBbM4iIZgECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwZvQIBwSCwaj8ikkhhoAjYAwXJKPS4Ahqp2WhAaLgDGdmwkNQcYsro4eazfxCscTggo5lPzYBjAHwNoAGZZRAgACX5IUIdGHwR3ZBRNk02IRgRJEYlKmkcdAIabRw2iY3cHAJ9CfUISdqUbAZYArABBADs=)
- произведение всех неприводимых полиномов в
![](data:image/gif;base64,R0lGODlhKQAZAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAIABAAlABIAhQAAAAAAAAAAHR0AAB0AHQAAMwAcSB0dSAAzWh1GbDMAADIAMjMeRzQ0HTMzWzNGRjNGbjNbgEgcAFozAEhZf11/f0huf2xGHW5GM39/XX9uSHtqRG5/WXd3XWZ3d2aIiIBbM4iIZgECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwaZQIBwSCwaj0jiJMBsFpASZlLINCQngqQEMR1erEOKNxDRdolg4yAx3Z6FaaKC2y4GBBYAKJCOCyV+R25EFwAXdEJfRk9nEkcDR35Zb4NEEmVFcQFFEGZGDZFDkEQEbYhCbAcAGF5gCk1NRQoAowCOiQGIm2hvcAAOf6dTgUgMekO3b8RJC8hVSRfPb3d5vdZDwNfaAAqT20RBADs=)
, степени которых делят n. Отсюда степень произведения всех неприводимых полиномов, степени которых делят n равна
![](data:image/gif;base64,R0lGODlhFQAYAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAIABAARABAAhQAAAAAAAB0AAB4eAB0AHR0AMgAAMwAdMgAdSB0dSAAzWh1GbDMAADIAHTIAMjMzWzNbgEgdHUgcAFozAEgzM1szM0ZGRll/WV1/f1luf0huf2xGHX9uSH9/XXtqRGZ3d2aIiIBbM4BuboiIZgECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwZFQIBwSCwaj5zChbE4Gi3OKATQjA6bFeswC2AgiIIAYBIwaIWDq/YwlGgnQw5BY3UMJwptYmi2bgKAeWd0Z0J7hQCAX2dBADs=)
. Число всех нормированных полиномов степени n в
![](data:image/gif;base64,R0lGODlhKQAZAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAIABAAlABIAhQAAAAAAAAAAHR0AAB0AHQAAMwAcSB0dSAAzWh1GbDMAADIAMjMeRzQ0HTMzWzNGRjNGbjNbgEgcAFozAEhZf11/f0huf2xGHW5GM39/XX9uSHtqRG5/WXd3XWZ3d2aIiIBbM4iIZgECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwaZQIBwSCwaj0jiJMBsFpASZlLINCQngqQEMR1erEOKNxDRdolg4yAx3Z6FaaKC2y4GBBYAKJCOCyV+R25EFwAXdEJfRk9nEkcDR35Zb4NEEmVFcQFFEGZGDZFDkEQEbYhCbAcAGF5gCk1NRQoAowCOiQGIm2hvcAAOf6dTgUgMekO3b8RJC8hVSRfPb3d5vdZDwNfaAAqT20RBADs=)
будет обозначаться
![](data:image/gif;base64,R0lGODlhJQAZAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAIABAAfABIAhQAAAAAAAB4AHh0AABwcHAAAHQAAMx0AMh0dSAAdSAAzWh0zWgAzWx1GbDMAADIAHTMAHTMAMzIAMjMeRzMzWzNGRjNGbjNZfzNbgEgcAEgdHUceM1ozAFszM11dRkhbSFl/WV1/f113d0Rqe0huf2xGHXd3XX9/XX9uSG5/WXd3ZmaIiIBbM4iIZgECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwECAwZ9QIBwSCwaj8ikMlkyLJ1KwXJ6RB2o2GFp6Ahgko/iwAvIBBrDq3CjhBIlAAhgyxWinkUWoDMk1adNRRwEQwhEDmgaeIdaRQ5CcEphRIZCk2lCAYcVA2hCHEWeAANFCkccCUZyU5FJokJSSo9KrUQRSbdIHAEFWb6/sr3ARkEAOw==)
.