Revisions to Solving/Reducing equations in $\mathbb{Z}/p\mathbb{Z}$

deleted 1 characters in body

Source Link

edited May 6, 2013 at 14:13

125.5k
11
407
581

The difference between $2^n$ and $n^2$ is that $2^n$ is not a function $\mod\; 10$$\bmod 10$ -- that is, $2^{n+10}$ is not congruent to $\;2^n\mod\;10$$2^n\bmod 10$. Further $2^n$ is only eventually periodic $\mod 10^k$$\bmod 10^k$, $k \geq 2$. For instance $2^1$ is not congruent to any other $2^n \mod 100$$2^n \bmod 100$. On the other hand, polynomial functions are all functions $\mod m$$\bmod\, m$ : f[n+m] is congruent to f[n]$\mod m$$\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 diophantineDiophantine 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.)

The difference between $2^n$ and $n^2$ is that $2^n$ is not a function $\mod\; 10$ -- that is, $2^{n+10}$ is not congruent to $\;2^n\mod\;10$. Further $2^n$ is only eventually periodic $\mod 10^k$, $k \geq 2$. For instance $2^1$ is not congruent to any other $2^n \mod 100$. On the other hand, polynomial functions are all functions $\mod m$ : f[n+m] is congruent to f[n]$\mod 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.)

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.)

improved formatting

Source Link

edited Jan 12, 2013 at 17:05

Artes

57.9k
13
159
247

The difference between 2^n$2^n$ and n^2$n^2$ is that 2^n$2^n$ is not a function mod 10$\mod\; 10$ -- that is, 2^(n+10)$2^{n+10}$ is not congruent to 2^n mod 10$\;2^n\mod\;10$. Further 2^n$2^n$ is only eventually periodic mod 10^k$\mod 10^k$, k >= 2$k \geq 2$. For instance 2^1$2^1$ is not congruent to any other 2^n mod 100$2^n \mod 100$. On the other hand, polynomial functions are all functions mod m$\mod m$ : f[n+m]f[n+m] is congruent to f[n] mod mf[n]$\mod 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^nSolve[ 2^n - n - q 10^k == 0 && 1 <= k <= 3 && 0 <= n < If[kIf[ 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 -> 361473786714651839609485931802192366508973300717001923159475447
1504248102862334079879518618873894396122749267837803515619997819988324
3404129619879532632910162314189970978766343329690527906605154864094201
3290819886814068}}
{{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 qq for k=3k=3 suggests that a practical limit is being reached. (I've had k=4k=4 running for over ten minutes, and it's time for me to move on.)

The difference between 2^n and n^2 is that 2^n is not a function mod 10 -- that is, 2^(n+10) is not congruent to 2^n mod 10. Further 2^n is only eventually periodic mod 10^k, k >= 2. For instance 2^1 is not congruent to any other 2^n mod 100. On the other hand, polynomial functions are all functions mod m: f[n+m] is congruent to f[n] mod 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 -> 361473786714651839609485931802192366508973300717001923159475447
1504248102862334079879518618873894396122749267837803515619997819988324
3404129619879532632910162314189970978766343329690527906605154864094201
3290819886814068}}

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.)

The difference between $2^n$ and $n^2$ is that $2^n$ is not a function $\mod\; 10$ -- that is, $2^{n+10}$ is not congruent to $\;2^n\mod\;10$. Further $2^n$ is only eventually periodic $\mod 10^k$, $k \geq 2$. For instance $2^1$ is not congruent to any other $2^n \mod 100$. On the other hand, polynomial functions are all functions $\mod m$ : f[n+m] is congruent to f[n]$\mod 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.)

added 1 characters in body

Source Link

edited Dec 16, 2012 at 23:27

Michael E2

244.8k
18
351
774

The difference between 2^n and n^2 is that 2^n is not a function mod 10 -- that is, 2^(n+10) is not congruent to 2^n mod 10. Further 2^n is only eventually periodic mod 10^k, k >= 2. For instance 2^1 is not congruent to any other 2^n mod 100. On the other hand, polynomial functions are all functions mod m: f[n+m] is congruent to f[n] mod m. In short, exponential functionfunctions 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 -> 361473786714651839609485931802192366508973300717001923159475447
1504248102862334079879518618873894396122749267837803515619997819988324
3404129619879532632910162314189970978766343329690527906605154864094201
3290819886814068}}

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.)

The difference between 2^n and n^2 is that 2^n is not a function mod 10 -- that is, 2^(n+10) is not congruent to 2^n mod 10. Further 2^n is only eventually periodic mod 10^k, k >= 2. For instance 2^1 is not congruent to any other 2^n mod 100. On the other hand, polynomial functions are all functions mod m: f[n+m] is congruent to f[n] mod m. In short, exponential function 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 -> 361473786714651839609485931802192366508973300717001923159475447
1504248102862334079879518618873894396122749267837803515619997819988324
3404129619879532632910162314189970978766343329690527906605154864094201
3290819886814068}}

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.)

The difference between 2^n and n^2 is that 2^n is not a function mod 10 -- that is, 2^(n+10) is not congruent to 2^n mod 10. Further 2^n is only eventually periodic mod 10^k, k >= 2. For instance 2^1 is not congruent to any other 2^n mod 100. On the other hand, polynomial functions are all functions mod m: f[n+m] is congruent to f[n] mod 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 -> 361473786714651839609485931802192366508973300717001923159475447
1504248102862334079879518618873894396122749267837803515619997819988324
3404129619879532632910162314189970978766343329690527906605154864094201
3290819886814068}}

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.)

Source Link

created Dec 16, 2012 at 14:40

Michael E2

244.8k
18
351
774

Loading

Stack Exchange Network

Return to Answer