View Single Post
Old 2021-03-07, 09:52   #960
Happy5214
 
Happy5214's Avatar
 
"Alexander"
Nov 2008
The Alamo City

12118 Posts
Default

Quote:
Originally Posted by henryzz View Post
I think the trick would be to prove that:
2^(2^3 * 3^2 * 5 * 7 * k + 1) - 1 == 1 mod d
3^(2^3 * 3^2 * 5 * 7 * k + 1) - 1) / 2 == 1 mod d
6^(2^3 * 3^2 * 5 * 7 * k) == 1 mod d

If this is true then s(6^(2^3 * 3^2 * 5 * 7 * k)) = (2^(2^3 * 3^2 * 5 * 7 * k + 1) - 1)*3^(2^3 * 3^2 * 5 * 7 * k + 1) - 1) / 2 - 6^(2^3 * 3^2 * 5 * 7 * k) = 1*1-1 mod d
To complete and streamline warachwe's proof, it's all provable by induction using Z_d. Note that the exponent constant resolves to 2520. 6^(2^3 * 3^2 * 5 * 7 * k) == 1 mod d relatively trivially (6^2520 = 1 mod d, and 1^k = 1 mod d for all integers k). To prove base 2, I translate it to the equivalent problem of solving 2^(2^3 * 3^2 * 5 * 7 * k + 1) = 2 mod d. In this case, 2^2521 (base case) = 2 mod d, and when 2^(2520*k+1) = 2 mod d, 2^(2520*(k+1)+1) = 2 mod d (since 2^2520 = 1 mod d and 2^(2520*(k+1)+1) = 2^(2520*k+1) * 2^2520). Similarly, 3^(2520*k+1) = 3 mod d for all integers k, a statement equivalent to the above formula in Z_d, so the three formulas are proved.

Last fiddled with by Happy5214 on 2021-03-07 at 09:54
Happy5214 is offline   Reply With Quote