Find large $n$ and calculate $r \equiv L \pmod{n}$ where $L = 999\,998\,997\dots003\,002\,001.$

Question

Update: I provided an answer but I tried something out with Python and I am kind of surprised. Computer technology today is more advanced than I can wrap my head around.

Instead of taking any residues at all I set my python program to directly add up all the terms in $L$,

$$ \Biggl [\sum_{n=0}^{498}\, \left(2001+2002\, n \right) {(10^{6})}^{n}\Biggl] + 999 \,{(10^{6})}^{499}$$

and then print out $L$. I expected the program to have serious problems number crunching, but it ran in a flash, printing

999998997996995994993992991990989988987986985984983982981980979978977976975974973972971970969968967966965964963962961960959958957956955954953952951950949948947946945944943942941940939938937936935934933932931930929928927926925924923922921920919918917916915914913912911910909908907906905904903902901900899898897896895894893892891890889888887886885884883882881880879878877876875874873872871870869868867866865864863862861860859858857856855854853852851850849848847846845844843842841840839838837836835834833832831830829828827826825824823822821820819818817816815814813812811810809808807806805804803802801800799798797796795794793792791790789788787786785784783782781780779778777776775774773772771770769768767766765764763762761760759758757756755754753752751750749748747746745744743742741740739738737736735734733732731730729728727726725724723722721720719718717716715714713712711710709708707706705704703702701700699698697696695694693692691690689688687686685684683682681680679678677676675674673672671670669668667666665664663662661660659658657656655654653652651650649648647646645644643642641640639638637636635634633632631630629628627626625624623622621620619618617616615614613612611610609608607606605604603602601600599598597596595594593592591590589588587586585584583582581580579578577576575574573572571570569568567566565564563562561560559558557556555554553552551550549548547546545544543542541540539538537536535534533532531530529528527526525524523522521520519518517516515514513512511510509508507506505504503502501500499498497496495494493492491490489488487486485484483482481480479478477476475474473472471470469468467466465464463462461460459458457456455454453452451450449448447446445444443442441440439438437436435434433432431430429428427426425424423422421420419418417416415414413412411410409408407406405404403402401400399398397396395394393392391390389388387386385384383382381380379378377376375374373372371370369368367366365364363362361360359358357356355354353352351350349348347346345344343342341340339338337336335334333332331330329328327326325324323322321320319318317316315314313312311310309308307306305304303302301300299298297296295294293292291290289288287286285284283282281280279278277276275274273272271270269268267266265264263262261260259258257256255254253252251250249248247246245244243242241240239238237236235234233232231230229228227226225224223222221220219218217216215214213212211210209208207206205204203202201200199198197196195194193192191190189188187186185184183182181180179178177176175174173172171170169168167166165164163162161160159158157156155154153152151150149148147146145144143142141140139138137136135134133132131130129128127126125124123122121120119118117116115114113112111110109108107106105104103102101100099098097096095094093092091090089088087086085084083082081080079078077076075074073072071070069068067066065064063062061060059058057056055054053052051050049048047046045044043042041040039038037036035034033032031030029028027026025024023022021020019018017016015014013012011010009008007006005004003002001

(use the slider bar)

That was amazing - you can find the remainder by directly dividing $L$ itself and not worrying about inserting any extra residue steps!

I will be going to summer school now to catch up with current technology.

---

For any $n \ge 1$ with there is a corresponding remainder $r$ obtained by dividing $L$ by $n$.

Now consider only $n$ satisfying

$\tag 1 n \lt 1000000$ $\tag 2 n \notin \{200000, 250000, 333333, 500000, 999999\}$

Calculate an explicit solution $(n,r)$ with $n$ as large as possible.

My Work

I became intrigued examining $L$ after seeing this question and giving an answer.

I think I know the best possible answer $(n,r)$ but it would be interesting to see what mathematics this question sparks; a computer program can be used if necessary for 'mop-up' operations.

Answer 1

The largest $n$ that satisfies the conditions is $n=999998$, and it shouldn't be too difficult to do that. We're looking for $$ L = 1 + 1000 \sum_{n=0}^{498} (3002+2002n)1000000^n $$ which modulo 999998 is the same as $$ L = 1 + 1000 \sum_{n=0}^{498} ( 3002+2002n) 2^n $$ To calculate this sum, first set $$ X = \sum_{n=0}^{498} 2^n \qquad\qquad Y = \sum_{n=0}^{498}n2^n $$ By standard formulas we get $$ X = \frac{2^{499}-1}{2-1} = 2^{499}-1 $$ and we can find $Y$ by a routine shifting trick: $$ 2Y+2X = Y - 0\cdot 2^0 + 499\cdot 2^{499} $$ or in other words $$ Y = 499\cdot 2^{499} - 2X = 497\cdot 2^{499} + 2 $$ Then $$ L = 1 + 1000(3002X + 2002Y) = 4004001 + 1000\cdot 2^{499}(3002\cdot 499 + 2002\cdot 497) $$ The only real task that remains is to compute $2^{499}$ modulo $999998$. Even with pencil and paper it shouldn't take more than one sheet to compute this by $$ a = 2^{15} = 32768 \\ b = 2^{30} = a^2 \\ c = 2^{31} = 2b \\ d = 2^{62} = c^2 \\ e = 2^{124} = d^2 \\ f = 2^{248} = e^2 \\ g = 2^{249} = 2f \\ h = 2^{498} = g^2 \\ i = 2^{499} = 2h $$ so just eight six-digit squarings or doublings with subsequent reductions modulo $999998$ (which is easy because $1000000\equiv 2$; one doesn't even need to do long division), and then three or four similar arithmetic operations to compute $L$.

I will leave the actual arithmetic to any reader who finds it worth his time.

Answer 2

Thanks to Henning Makholm and fleablood for helping me see the true power of modular arithmetic - and exponents be damned!

The key idea is you don't want to apply $\text{mod}(n)\text{-Residue}$ to get the remainder of an already big number like $10^{100}$. Instead you use recursion, defining $p_0 = 1$ and for $k \ge 0$,

$$ p_{k+1} = [10^6 \times p_k]\; \text{mod}(n)\text{-Residue}$$

and you can then fold-in $\;p_{100}$ for $10^{100}$ in the remainder calculation.

Here is a python program to calculate remainders for that, now not so scary, large number $L$.

CODE

M = 1000000

def bP(i):
    p = 1
    for j in range(0, i):
        p = (p * M) % n
    return p

def getTerm(i):
    return ((2001 + 2002 * i) * bP(i)) % n

while True:
    print()
    n = int(input('Please input divisor: '))
    if n == 0:
        raise SystemExit
    r = 0
    for i in range(0, 499):
        r = (r + getTerm(i)) % n
    r = (r + 999 * bP(499)) % n
    print('Divisor =', n, 'Remainder =', r)

OUTPUT

Please input divisor: 13
Divisor = 13 Remainder = 6

Please input divisor: 999998
Divisor = 999998 Remainder = 487763

Please input divisor: 59470
Divisor = 59470 Remainder = 42391