# Solving/Reducing equations in $\mathbb{Z}/p\mathbb{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\;$?

-
This is how it would be done in Maple: msolve(2^n = n, 100); {n = 36} –  user5050 Dec 16 '12 at 11:08

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.

-
Reduce[ Mod[ 2^n - n, 10^k] == 0 && 10^(k-1) < n < 10^k, n, Integers] gives me the same error for k>=5. But in general, shouldnt this be evaluated almost immediately? –  CBenni Dec 9 '12 at 17:54
@CBenni You might play around e.g. with this : Table[ Reduce[ Mod[2^n - n, 10^4] == 0 && k 10^(4) < n < (k + 1) 10^(5 - 1), n, Integers], {k, 10}], while for Mod[2^n - n, 10^5] there is only n == 48736. –  Artes Dec 10 '12 at 2:25

The difference between $2^n$ and $n^2$ is that $2^n$ is not a function $\bmod 10$ -- that is, $2^{n+10}$ is not congruent to $2^n\bmod 10$. Further $2^n$ is only eventually periodic $\bmod 10^k$, $k \geq 2$. For instance $2^1$ is not congruent to any other $2^n \bmod 100$. On the other hand, polynomial functions are all functions $\bmod\, m$ : f[n+m] is congruent to f[n]$\bmod\, m$. In short, exponential functions do not behave in the nice way polynomial functions do.

Instead of solving it as a modular equation, convert it to an explicit Diophantine equation:

Solve[ 2^n - n - q 10^k == 0 && 1 <= k <= 3 && 0 <= n < If[ k == 1, 2, 1] 10^k,
{k, n, q}, Integers]

{{k -> 1, n -> 14, q -> 1637}, {k -> 1, n -> 16, q -> 6552},
{k -> 2, n -> 36, q -> 687194767}, {k -> 3, n -> 736,
q ->  3614737867146518396094859318021923665089733007170019231594754471\
5042481028623340798795186188738943961227492678378035156199978199883243\
4041296198795326329101623141899709787663433296905279066051548640942013\
290819886814068}}


The size of the quotient q for k=3 suggests that a practical limit is being reached. (I've had k=4 running for over ten minutes, and it's time for me to move on.)

-