 mersenneforum.org How to solve: k(b^m)-z=n*d. ?
 Register FAQ Search Today's Posts Mark Forums Read  2018-03-09, 04:05   #12
carpetpool

"Sam"
Nov 2016

4768 Posts Quote:
 Originally Posted by JM Montolio A Solve: 29(5^m)-11 = 13*D
This can be done with basic algebra and modular math.

To get a set of basic solutions (m, D) write out:

29*5^m-11 = 0 (mod 13)

29*5^m = 11 (mod 13)

5^m = 8 (mod 13)

m = 3 (mod 4).

So for any integer n,

m = 3*n+4, D = (29*5^(3*n+4)-11)/13

will be a solution to

29(5^m)-11 = 13*D

as you put it.   2018-03-09, 05:00   #13
CRGreathouse

Aug 2006

2·2,969 Posts Quote:
 Originally Posted by JM Montolio A 29(5^M)-11=13D.
The solutions are M = 4k + 3, D = (3625*625^k - 11)/13.

If b and n are relatively prime, you can find the general solutions to k(b^m) - z = nd by finding the order of b mod n, computing k(b^m) - z for m from 1 to the order, and taking any values which result in 0; these values, plus an arbitrary variable k times the order, are the possible values of m (and the d values can be computed from them).

The case where b and n have a common divisor is not essentially different; you check the small cases, where some p | b and p^e | n, but p^e does not divide b, individually, then look at the order of b with all the common primes divided out mod n with all the common primes divided out.

In the first case you could have 0 solutions or infinitely many; in the second case you could have finitely many or infinitely many.

Edit: see carpetpool's post above.

Last fiddled with by CRGreathouse on 2018-03-09 at 05:01   2018-03-09, 05:43 #14 axn   Jun 2003 17×281 Posts OP sounds suspiciously like they're trying to sieve k*b^n+c form (variable n), in which case, just use newpgen or srsieve   2018-03-09, 09:12 #15 JM Montolio A   Feb 2018 6016 Posts Are the cumulative product of (B^g). Last step not.   2018-03-09, 09:20 #16 JM Montolio A   Feb 2018 6016 Posts Are the cumulative product of (B^g). Starting with 1. And not the last step. Thats gives "bits one of D"="number steps". Rules are related to tserie used. Mersenne is tserie "n+e = (2^g)(e')". Most general: n+e=(B^g)(e') Any tserie as a equation. For Mersenne, (eLast)(B^M)-(eStart)=n*D. Collatz is also a tserie. 1+3e=(2^g)(e'). But there are others tserie. Thanks for your interest. JMM   2018-03-09, 13:50   #17
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts Quote:
 Originally Posted by carpetpool This can be done with basic algebra and modular math. To get a set of basic solutions (m, D) write out: 29*5^m-11 = 0 (mod 13) 29*5^m = 11 (mod 13) 5^m = 8 (mod 13) m = 3 (mod 4). So for any integer n, m = 3*n+4, D = (29*5^(3*n+4)-11)/13 will be a solution to 29(5^m)-11 = 13*D as you put it.
3 mod 4 is actually 4n+3.   2018-03-09, 15:29   #18
carpetpool

"Sam"
Nov 2016

2·3·53 Posts Quote:
 Originally Posted by science_man_88 3 mod 4 is actually 4n+3.
Too late to fix it but thanks for pointing out.   2018-03-09, 15:32   #19
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts Quote:
 Originally Posted by carpetpool Too late to fix it but thanks for pointing out.
In fact you can prove D is 18 mod 20 fairly quickly. Etc.   Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post ixfd64 Puzzles 4 2011-03-30 12:25 flouran Miscellaneous Math 23 2009-01-04 20:03 davar55 Puzzles 3 2008-10-09 00:35 nuggetprime Miscellaneous Math 1 2007-06-26 22:04 davar55 Puzzles 52 2007-06-26 21:41

All times are UTC. The time now is 11:30.

Wed Nov 25 11:30:37 UTC 2020 up 76 days, 8:41, 4 users, load averages: 2.05, 1.73, 1.67