Problems & Puzzles:
K. Crump (*) sent the following problem:
Consider the equation:
2^n = 2^(2^z+1) mod n
Where: n = 2^(z*p)+1, prime p > 2 & z is any positive integer
1 - Prove or Disprove the equation always holds for z<=4.
2 - Prove or Disprove the
equation always holds when p = 1 mod (z-1).
Joe is author of a very nice and interesting Add-in
for Excel - freely downloadable - capable of handling the most of the
usual functions of Number Theory. I'm sure that you'll enjoy it as I do.
To use it, do this:
1) Download it to your PC to: c:\windows\ApplicationData\Microsoft\Addins
2) Open your Excel
3) Active the ZMath add-in: Tools,
Add-in, Zmath, Accept
4) To see all the available functions:
click the fx button, take the Zmath functions and browse for all the
available functions in the right window.
Joe recommends the following way:
1 - Copy it somewhere on your harddrive,
2 - In Excel 97, 2000, or XP, choose File/Open
3 - Navigate to "C:\" or just type in "C:\zzmath.xll"
and click OK.
4 - The addin will be loaded. Click 'Enable Macros' if prompted.
5 - Type =ZAdd(123,456) in a cell to verify it is working.
The only exception is if you are using Excel XP and your Macro security is
set to 'High', then the addin won't load and you won't get a warning. Go
to Tools menu, Macro submenu, and click 'Security' to change it to
'Medium' if you are using Excel XP.
Eric Brier solved
completely this problem. Here is the paper (a
pdf file) he sent the 23/9/22.
I asked to both, Crump and Brier,
what was their respective interest in this equation and problem. Here are
and figured it would be an interesting problem for your site.
It was just of something I ran across empirically during my
computational attack on 2^n mod n = c equations [
If you or Eric are interested, a related problem with a lot of
attention associated with it (but much harder to solve) is whether for
every c > 1 there is at least one solution n to 2^n mod n = c. This would
be something of interest to a lot of number theorists.
I'm preparing to setup a challenge on my web-site offering $50 (US) for
a proof to the above. And $25 for a solution to 2^n mod n = 465. The least
'c' for which no solution is currently known is c=465 resisting a strong
search thus far.
I was interested by this problem because congruences are related to my
work in cryptography and this kind of properties looked rather strange at
the first sight.