(41) Exponentiation & Residue Reduction

[Thomas Klemm]

Errata

342 Appendix

This is the binary decomposition of the exponent 340.

Check: \(2^8 + 2^6 + 2^4 + 2^2 = 340\). Check!

Next, the computer will start the necessary repeated squarings and
reductions modulo 341, which will take about 7 seconds. Then the display
will show the end result, a 1 (without a decimal point!).
Thus,

\(
\left< 2^{340} \right>_{341} = 1
\).

In other words, 341 is a pseudoprime to the base 2.

Similarly, after pressing 2, ENTER, 170, ENTER, 341, R/S, the display
shows in succession:

7.      5.      3.      1.            1

where that last display (the 1 without the decimal point) tells us that

\(
\left< 2^{170} \right>_{341} = 1
\).

Proceeding in the same manner, we find

\(
\left< 2^{85} \right>_{341} = 32
\),

i.e., 341 is not a strong pseudoprime to the base 2. Also, by using 3 as a base
we find

\(
\left< 3^{340} \right>_{341} = 56
\).

Thus, 341 is certainly not an absolute pseudoprime (Carmichael number).

However, for the modulus 2821, we find

\(
\left< 2^{2820} \right>_{2821} = \left< 3^{2820} \right>_{2821} = 1
\),

two of the many steps necessary to show that 2821 is an absolute pseudoprime
or a Carmichael number.

Note that our little calculator with a limited accuracy and a 10-digit
display, in calculating \(\left< 2^{2820} \right>_{2821}\) has coped with a number having 1346
decimal digits! This has been made possible by the frequent intermediate
modulo reduction that the program employs.

Appendix 343

Original program for the HP-41C:

Code:

01 LBL "AN"        ; call program
02 SF 29           ; decimal point
03 STO 18          ; store modulus
04 RDN             ; get exponent
05 STO 17          ; store exponent
06 RDN             ; get base
07 STO 16          ; store base
08 2               ; constant
09 STO 01          ; store 2
10 LN              ; take logarithm
11 STO 15          ; store log
12 FIX 0           ; display no fractions
13 1               ; constant
14 STO 14          ; store 1
15 0               ; constant
16 STO 02          ; store 0
17 LBL 10          ; subroutine for calculating
18 RCL 17          ; binary representation of ?
19 LN
20 RCL 15
21 /
22 0.000000001     ; add small constant to
23 +               ; avoid inaccurate rounding
24 INT
25 ENTER
26 ST- IND 01
27 PSE             ; display the binary
28 1               ; exponents of ?
29 ST+ 01
30 RDN
31 STO IND 01
32 2
33 X<>Y
34 Y^X
35 ST- 17
36 RCL 17
37 X=0?            ; binary representation
38 GTO 11          ; of ? completed?
39 GTO 10
40 LBL 11          ; subroutine for executing
41 RCL IND 01      ; repeated squaring
42 X=0?
43 GTO 12
44 RCL 16
45 RCL 18
46 2
47 /
48 X<>Y
49 X>Y?
50 XEQ 16
51 X^2
52 RCL 18
53 MOD             ; take remainder
54 STO 16          ; modulo ?
55 1
56 ST- IND 01
57 GTO 11
58 LBL 12          ; subroutine for cal-
59 RCL 16          ; culating intermediate
60 ST* 14          ; squaring results
61 RCL 14
62 RCL 18
63 MOD
64 STO 14
65 1
66 ST- 01
67 RCL 01
68 2
69 X=Y?
70 GTO 13
71 GTO 11
72 LBL 16
73 RCL 18
74 -
75 RTN
76 LBL 13          ; Subroutine for
77 RCL 14          ; recalling and
78 CF 29           ; displaying residue
79 STOP            ; display residue
80 GTO "AN"        ; ready to start over
81 RTN
82 END

Translated program for the HP-42S:

Code:

00 { 141-Byte Prgm }
01▸LBL "AN"
02 SF 29
03 STO 18
04 R↓
05 STO 17
06 R↓
07 STO 16
08 2
09 STO 01
10 LN
11 STO 15
12 FIX 00
13 1
14 STO 14
15 0
16 STO 02
17▸LBL 10
18 RCL 17
19 LN
20 RCL 15
21 ÷
22 0.000000001
23 +
24 IP
25 ENTER
26 STO- IND 01
27 PSE
28 1
29 STO+ 01
30 R↓
31 STO IND 01
32 2
33 X<>Y
34 Y↑X
35 STO- 17
36 RCL 17
37 X=0?
38 GTO 11
39 GTO 10
40▸LBL 11
41 RCL IND 01
42 X=0?
43 GTO 12
44 RCL 16
45 RCL 18
46 2
47 ÷
48 X<>Y
49 X>Y?
50 XEQ 16
51 X↑2
52 RCL 18
53 MOD
54 STO 16
55 1
56 STO- IND 01
57 GTO 11
58▸LBL 12
59 RCL 16
60 STO× 14
61 RCL 14
62 RCL 18
63 MOD
64 STO 14
65 1
66 STO- 01
67 RCL 01
68 2
69 X=Y?
70 GTO 13
71 GTO 11
72▸LBL 16
73 RCL 18
74 -
75 RTN
76▸LBL 13
77 RCL 14
78 CF 29
79 STOP
80 GTO "AN"
81 RTN
82 END

Resources

• Number Theory in Science and Communication
• Back Matter: Pages 341-374