options - Solving/Reducing equations in $mathbb{Z}/pmathbb{Z}$

I was trying to find all the numbers $n$ for which $2^n=n\mod 10^k$ using Mathematica. My first try:

Reduce[2^n == n, n, Modulus -> 100]

However, I receive the following error:

Reduce::nsmet: This system cannot be solved with the methods available to Reduce. >>

using $n^2$ instead of $2^n$ works just fine, where is the problem with $2^n\;$?

On top of that, how do I keep the modulus $10^k$ variable and therefore, receive a solution dependent on $k\;$?

Answer

The problem we encounter here is an instance of rather unexpected limitations of equation solving functionality (i.e. Modulus option in Reduce), e.g. this question : Strange behaviour of Reduce for Mod[x,1] provides another example which has been fixed in the newest version (9.0) of Mathematica. Since Modulus unexpectedly doesn't work here we can take advantage of the Mod function. The main issue here is that there are infinitely many solutions and even though one might classify them easily, the task of finding a general solution is not straightforward in Mathematica. Taking this into account one should assume some bounds on n. If we do so, given a small integer k > 0, we can find all solutions in a given range, e.g. for k == 2 :

Reduce[ Mod[ 2^n - n, 100] == 0 && 0 < n < 10^3, n, Integers]

n ==  36 || n == 136 || n == 236 || n == 336 || n == 436 || n == 536 ||

n == 636 || n == 736 || n == 836 || n == 936

Increasing the range of n we might ensure that the general form of the solution for k == 2 should be n == 100 m + 36 for m ∈ Integers && m >= 0 and then we could proceed in order to prove an appropriate mathematical theorem. For a general k >= 1 the space of possible solutions to be explored is much wider, and restricting k e.g. this way 0 < k < n < 10^3 it takes much more time to find all solutions :

Reduce[ Mod[ 2^n - n, 10^k] == 0 && 0 < k < n < 10^3, {k, n}, Integers]

while for e.g. 0 < k < 10 < n < 10^3 we get the results almost immediately :

Solve[ Mod[ 2^n - n, 10^k] == 0 && 0 < k < 10 < n < 10^3, {k, n}, Integers] // Short

{ { k -> 1, n -> 14}, {k -> 1, n -> 16}, {k -> 1, n -> 34},

  <<105>>, {k -> 2, n -> 836}, {k -> 2, n -> 936}, {k -> 3, n -> 736}}

Edit 1

Assuming n in a finite range we can still encounter messages, that the system cannot be solved e.g. :

Reduce[ Mod[ 2^n - n, 10^5] == 0 && 10^(5 - 1) < n < 10^5, n, Integers]

Reduce::nsmet: This system cannot be solved with the methods available to Reduce. >>

A workaround (not very convenient) would be dividing the range 10^(5 - 1) < n < 10^5 into e.g. 9 equal ranges m 10^4 < n < (m + 1) 10^4 for integer m : 1 <= m <= 9. A more systematic approach takes advantage of one of many SystemOptions like ExhaustiveSearchMaxPoints (there is no separate documentation page for this option, nevertheless one finds necessary information here Diophantine Polynomial Systems ), which by default is :

SystemOptions[ "ReduceOptions" -> "ExhaustiveSearchMaxPoints"]

{"ReduceOptions" -> {"ExhaustiveSearchMaxPoints" -> {1000, 10000}}}

increasing the last value we can find the only solution in a given range :

SetSystemOptions["ReduceOptions" -> "ExhaustiveSearchMaxPoints" -> {1000, 100000}];
Reduce[ Mod[ 2^n - n, 10^5] == 0 && 10^(5 - 1) < n < 10^5, n, Integers]

n == 48736

to solve e.g. Mod[ 2^n - n, 10^6] == 0 && 10^(6 - 1) < n < 10^6 we need to increase ExhaustiveSearchMaxPoints even more , e.g. (it takes a few minutes to evaluate) :

SetSystemOptions[ "ReduceOptions" -> "ExhaustiveSearchMaxPoints" -> {10^6, 10^6}];
Reduce[ Mod[ 2^n - n, 10^6] == 0 && 10^(6 - 1) < n < 10^6, n, Integers]

n == 948736

Edit 2

To prove a more general theorem we can use the results we've got so far. Assuming this form of the general solution for k == 2 : n == 100 m + 36 for m ∈ Integers && m >= 0 we can demonstrate working with Resolve that in fact it is a solution in much wider range than we could do this with Reduce as above. Unfortunately we can't prove with Mathematica that it is a solution for all natural m because we have to assume a lower and upper bound, e.g. (evaluating it takes a few minutes) :

Resolve[ ForAll[ m, 0 < m <= 10^5 && m ∈ Integers, 
                 Mod[ 2^(100 m + 36) - 100 m - 36, 100] == 0]]

True

Increasing ExhaustiveSearchMaxPoints we found ~ 10000 solutions, while this way we showed that the result is true for all natural m <= 10^5 in approximately the same time.