Операторы в PARI/GP

[genk]

Коллеги.подскажите,пожалуйста,как в PARI работает оператор "x%n" для натурального n и рационального x=p/q.Например, 3/7%15=9, 13/5%7=4, 56/3%7=0,а применение 4/9%6 вовсе выдает ошибку.Сходу как-то не разобрался в алгоритме вычисления.

[Dmitriy40]

Оно представляет $x=p/q$ как $p\cdot q^{-1}$, что в общем-то пока правомочно. Но при накладывании условия $x \pmod{n}$ выходит следующее: $x \pmod n = p\cdot q^{-1}\pmod n=p\cdot(q^{-1}\bmod n)\pmod n$ и вот тут уже $q^{-1}$ начинает пониматься не как вещественное (или рациональное) число $1/q$, а как обратный элемент к $q$ в кольце по модулю $n$ (т.е. такое что $q^{-1} \cdot q = 1\pmod n$). Ну а такового не существует если $\gcd(q,n)>1$ -- вот и ошибка при попытке его вычислить.

Если Вам не критично получение в результате именно рационального числа, то переходите к вещественному числу $x=p/q$ и уже от него берите остаток по модулю. Или домножением x на 1. (именно с точкой!), или в модуле n укажите вещественное число (с точкой). Что забавно результат может отличаться в последнем знаке на 1.

Сохранить рациональность ответа у меня получилось так: x%n=frac(x/n)*n

[genk]

Dmitriy40
Да,с кольцом $\mathbb{Z_\mathbf{n}}$ все понятно.Видимо, PARI ориентирован на модульную арифметику.Собственно,мой вопрос возник вот по какому поводу.В одном из ваших сообщений(не помню где,но по числам Мерсенна) у Вас в коде(я уж пишу по наброскам в строку)

forstep(x=3,100000,2,t=x;v=[];for(n=2,16,m=2^n-1;while(t%m==0,t=t/m;v=concat(v,m)));if(t==1,print(x,":",v)))

есть фрагмент "t%m",тестирующий,как я понял,t на кратность m.Но мне не совсем понятен алгоритм цикла while() внутри цикла for().Допустим,$x=9$.Тогда при первой итерации станет $v=[3]$.И как дальше алгоритм выходит на $v=[3,3]$,что значится на выходе $9:[3,3]$?

[Dmitriy40]

genk в сообщении #1593299 писал(а):

Но мне не совсем понятен алгоритм цикла while() внутри цикла for().Допустим,$x=9$.Тогда при первой итерации станет $v=[3]$.И как дальше алгоритм выходит на $v=[3,3]$,что значится на выходе $9:[3,3]$?

Так на первой итерации $t=9$ делится на $m=2^2-1=3$ и потому t становится равным $9/3=3$, в v[] записывается $3$. На второй итерации while $t$ всё ещё делится на $3$ и потому оно снова на него делится и в v[] снова добавляется $3$. На третьей итерации $t=1$ уже не делится на $m=3$ и потому цикл while завершается с $v=[3,3]$.
Цикл while исключает делитель $m$ из числа $t$, причём столько раз в какой степени он туда входит, перечисляя их в v[]. А так как $m$ пробегает только по числам вида $2^n-1$, то и делители исключаются только такого вида. И если число $x=t$ состоит только из них, выводится результат на экран. Не знаю/помню где и зачем такое было нужно.

[genk]

Dmitriy40