mersenneforum.org > Math Modified Fermat's theorem
 Register FAQ Search Today's Posts Mark Forums Read

2017-11-12, 17:25   #12
Dr Sardonicus

Feb 2017
Nowhere

24×3×7×19 Posts

Quote:
 Originally Posted by devarajkandadai Sure: consider Mod(x,x^2+97). Let this be %1. You have to calculate ((2+%1)^(101^2-1)/101. Thank you.
Apart from your command not parsing, your polmod is not prime to p = 101 as per your hypothesis
Quote:
 Originally Posted by devarajkandadai Of course a and p have to be coprime.
Obviously 2 + Mod(x, x^2 + 97) = Mod(x + 2, x^2 + 97), and

Mod(x + 2, x^2 + 97)*Mod(x - 2, x^2 + 97) = Mod(x^2 - 4, x^2 + 97) = Mod(-101, x^2 + 97).

Last fiddled with by Dr Sardonicus on 2017-11-12 at 17:33 Reason: Adding additional quote

2017-11-12, 17:59   #13
CRGreathouse

Aug 2006

22×3×499 Posts

Quote:
 Originally Posted by devarajkandadai Sure: consider Mod(x,x^2+97). Let this be %1. You have to calculate ((2+%1)^(101^2-1)/101. Thank you.
You are doing this:
Code:
Mod(x+2,x^2+97)^(101^2-1)/101
But you should be doing this instead:
Code:
Mod(Mod(x+2,x^2+97), 101)^(101^2-1)
which shows that the result does have a remainder and so is not divisible by 101. This is much faster and won't cause the stack to explode.

2017-11-12, 19:19   #14
Dr Sardonicus

Feb 2017
Nowhere

24×3×7×19 Posts

Quote:
 Originally Posted by CRGreathouse You are doing this: Code: Mod(x+2,x^2+97)^(101^2-1)/101 But you should be doing this instead: Code: Mod(Mod(x+2,x^2+97), 101)^(101^2-1) which shows that the result does have a remainder and so is not divisible by 101. This is much faster and won't cause the stack to explode.
Hmm. I tried the command

r=Mod(x+2,x^2+97)^(101^2 - 1);

(the last semicolon prevents PARI from barfing r all over the screen), and it completed without error in less time than could be reported. I checked, and trace(r) had over 10,000 decimal digits, so yeah, it's unnecessarily big.

My old version balked at Mod(Mod(x+2,x^2+97), 101), but Mod(x+2,x^2+97)*Mod(1,101) was fine:

Code:
? Mod(Mod(x+2,x^2+97),101)
*** Mod: incorrect type in Rg_to_Fl.

? Mod(x+2,x^2+97)*Mod(1,101)
%1 = Mod(Mod(1, 101)*x + Mod(2, 101), x^2 + 97)

? %^(101^2 - 1)
%2 = Mod(Mod(76, 101)*x + Mod(51, 101), x^2 + 97)
As can be seen, it isn't 1...

2017-11-12, 20:04   #15
CRGreathouse

Aug 2006

10111011001002 Posts

Quote:
 Originally Posted by Dr Sardonicus My old version balked at Mod(Mod(x+2,x^2+97), 101), but Mod(x+2,x^2+97)*Mod(1,101) was fine
Oh yes, I forgot that was the old way to do it. It works just as well.

 Similar Threads Thread Thread Starter Forum Replies Last Post devarajkandadai Number Theory Discussion Group 12 2017-12-25 05:43 devarajkandadai Number Theory Discussion Group 1 2017-07-07 13:56 devarajkandadai Number Theory Discussion Group 0 2017-06-24 12:11 devarajkandadai Number Theory Discussion Group 2 2017-06-23 04:39 Citrix Math 24 2007-05-17 21:08

All times are UTC. The time now is 04:35.

Thu Jun 1 04:35:37 UTC 2023 up 287 days, 2:04, 0 users, load averages: 0.91, 1.00, 1.14