to:don.lotto@paradise.net.nz, rusin@vesuvius.math.niu.edu
from: don.lotto@paradise.net.nz
subject: clock arithmetic [LONG 7pp.]

Dave Rusin, greeting.
Re: 1580,187,223 divides 10^9e9 +3.  Sci.math
regards don.mcdonald@paradise.net.nz


    1991, WED 4 September.  REF.  DSMCDO230891. 
    CLOCKAR, FRI 6.9.91, 1600, (1411 words.) 
         14/5/1995. 
    WED 16.10.91,  SUN 3 Nov 91, 1455, (1526 
    words.) FRI 31.1.92, 2250, (1554 words.) 
         Thur 19.3.92, 2015-2040, (1654 words.) 
         TUES 7.4.92, 21.4.92, (1832 words.) 
    Thurs 2.7.92, (1873 words.)  09.11.01 2oo1.*
     
    CLOCK  (MODULAR) ARITHMETIC,   
     by Donald S  McDonald, 
    F 63/*3*  Hut.chi.son Rd, Wellington 2, New
    Zealand,  Teleph. +64(4) 389-6820. 
    BBC/Acorn Computer User Group (NZ) Inc. 
     
    Abstract. 
     
    When we look at a clock, we 'throw away' 
    100's of years of past time, and look at just 
    the 'hours' or 'minutes' of the present day. 
    Example.  11.30 a.m. plus 1 hr 45 min = 1.15 
    p.m.  It is similar with days of the week, 
    days of the year, feet and inches and chains, 
    etc.: 
     
    When is 7002 days after WED 4 September, 1991 
    ?  One thousand whole weeks, plus 2 days.  
    Hence, FRIDAY. 
     
    The exacting requirements of divisibility of 
    large prime number calculations makes 
    extensive use of Clock (Modular) Arithmetic. 
     
     
    What is a factor of 10^6-1 ? 
    (After I chose this number, I saw it given 
    with more difficult examples, in Number 
    Theory and its History, by Eystein Ore. Dewey 
    class, 512.81.) 
    10^6 = 1E6 = 1 million. 
      Write your answer ... 
    = 999,999 = 9x111 x 1001 
    = 3x3 x 3x37   x  7x11x13. 
     
    OR,  =99 x 10,101 
    = 3x3x11  x  3x 3367 
    3367 = 7x481,    481 = 13x37. 
     
    The set of prime factors that a number may 
    ultimately be reduced to, is UNIQUE for that 
    number.   (This is called The Fundamental 
    Theorem of Arithmetic.) 
     
    The number, R(317) = 11,111, ..., 111  (317 
    digits), is the 4th and largest known Repunit 
    prime.  (REP. UNIT). (Wells, Penguin 
                                    Page 1
    dictionary.) 
     
     
    Clock Arithmetic. 
     
    {    37                       } 
    [  10  ] [  10  ] [  10  ] (+7) 
     
    If we mark off lengths of ten (10) units 
    against 37   =  3x10 +7,  Then, the part left 
    over equals 7 units. 
     
      On a clock circle :   O + O + O  + ). 
    I.e. 3 closed circles (of 10 each) and a part 
    circle of 7 units. 
    IN BBC BASIC , We have Congruence (Modulus) 
    arithmetic functions: 
     
    37  DIV  10,  equals 3.   i.e. 3x10 
    37  MOD  10,  equals 7.   i.e.  7 
                             Total = 37. 
    When we look at a clock, we 'throw away' 
    100's of years of past time, and look at just 
    the 'hours' or 'minutes' of the present day. 
     
    A different question. 
    When is 7002 days after WED 4 September, 1991 
    ? 
     
    Well,  7 days after is Next Wednesday. 
    7000 days after is a much later WEDNESDAY.  
    (1000 whole weeks.) 
    7002 days is 2 days more,  Therefore a 
    Friday, etc. 
     
    Algebra. 
     
    (a^6 - 1)  =  (a^3-1)(a^3+1), "Square minus a 
    square." 
    = (a-1)(a^2+a+1).(a+1)(a^2-a+1),  factors. 
         "Cube  + or - cube." 
     
    Example.  25^2 - 23^2  =  625 - 529  = 96 
    =  (25-23) (25+23)  = 2 x 48. 
    Turn this page upside down.  The equation 
    reads identically, rotated through 180 
    degrees! 
      ( 96 = 625-529 )  
     
    The only numbers like (a^6-1) that can be 
    prime are numbers:  M(p)= 2^prime - 1, 
    Mersenne. 
    Compare song, Inchworm:  2+2, 4+4, 8+8, 
    16+16, 32+32, ... 
     
    A prime number is any positive integer 
    greater than 1 which is not evenly divisible 
                                    Page 2
    by any factor except itself and unity.  
    Example 7, only divisible evenly by 7 and 1. 
     
    The only numbers like (a^3 +1) that can be 
    prime are numbers: F(N) =  2^(2^N) +1,  
    Fermat.  Compare ANZ Bank, TV ad, August 
    1991:  2x2, 4x4, 16x16, 256x256, ...
    wrong XXXX
    perhaps a^(2^n) + b(2^n).  XXX
     
    Mersenne Numbers,  M(p) = 2^prime -1, are not 
    always prime. 
    M(p) is prime for p = {1, 2, 3, 5, 7, 13, 17, 
    19, ...}. 
    BUT,  M(11) = 2^11-1  = 2047  = 23x89 is NOT 
    prime. 
    M(61)  = 2^61 -1 IS prime, (proved in 1883). 
    M(257)  = 2^257 -1,  is NOT prime. 
     
    "NOT PRIME" numbers are called COMPOSITE. 
     
     
    The largest known prime number in 1985 was: 
    M(216,091)  =  2^216091  -1. 
     
    The number of primes NEVER ENDS,  (IS 
    INFINITE.)  An elegant proof of this theorem 
    dates from Greek mathematician Euclid.  And a 
    new record prime number was set in 1989.  
    (Guinness Book of Records, 1991.)  Here it is 
    W = 391,581*2^216,193-1. 
     
    So I tried to CHECK it,  a formidable task ! 
     
    Well, it has 65,087 decimal digits, has this 
    prime number.  So, I pushed my BBC model-B 
    microComputer up to factors as high as 92,681 
    , and I could not find any factor which 
    divided evenly into the prime. 
     
    I doubled the prime number and added 1.  I 
    found 3 factors of (2W+1):.  59, 167,  18979. 
    I doubled again and added another 1,  =  4W + 
    3,  where W was the original prime number. 
     
    I found factors,  7, 6199, and 92219, of (4W 
    + 3).  Neither (2W+1) nor (4W+3) can be prime 
    in the case that they have smaller prime 
    factors.  BBC BASIC 2 Programs "CABIN4", by D 
    S McDonald, 1989, can factor numbers :  
    C*A**B +/- N.  
     
    (N.B. A new record prime number, M756839, has 
    just been published in NATURE Journal, 
    26.3.92.  See References.  And M_859433 in 
    early 1994.) 
     
    I thought, can I discover my own, (a smaller) 
    number, and invent a proof that it is prime ? 
                                    Page 3
     
    So, I have been thinking of 2 numbers, viz.  
    2^210  plus or minus 3.  So far, I suspect 
    that the larger number,  2^210 + 3, is 
    Composite, But has no factors less than 
    92,681  = 2^16.5. 
     
    The Reader in Mathematics at Victoria 
    University of Wellington, said to me 
    (3.9.1991, yesterday), "We haven't got a 
    number theorist at Victoria University, who 
    can check your work." 
     
     
    Factorising 2^120 -1. 
     
    M(120) = 2^120-1 = 1.3E36, approximately,, 
    has many factors -- 120 has many factors.  
    It, M(120), has 10 prime factors which end in 
    digit "1", and others.  Some prime factors 
    multiplied in pairs also end in 1:  21, 51,  
    91. 
     
    I have resolved this number completely into 
    its prime factors and its highest prime 
    factor was greater than 2^32.  I.e.  greater 
    than BBC Basic 4-byte integers. 
     
    Here it is, M(120) = 3.3.7.11.31.151.331 x 
    5.5.13.41.61.1321 x 17.241.61681 x 
    4,562,284,561. 
     
     
    Testing 2^210 + or - 3. 
     
    Product equals 2^420 - 9. 
    210 = 26x8 + 2,  420 = 26x16 + 4. 
    2^420 = (2^26)^16 x16. 
     
    To test if 2^420 = 9 mod p, (p ranges over 
    the odd integers),  we start with:   T = 2^26 
     (over 67 million = 67,108,864.) And Square 
    the result repeatedly. 
    S = T,  S = S*S,  S = S*S, .... 
    Before each squaring, calculate remainder , S 
    MOD P,  then square the remainder. 
     
    Since we square S, (S = S*S), the initial S 
    cannot exceed 2^15.5;  S Squared < 2^31, 
    4-byte integers. 
     
    Then we can only test factors up to, p = 
    2^15.5 = 46,341. 
     
    I use NEGATIVE MODULUS  (Least Absolute 
    Modulus), like 31 minutes past 12 noon 
    o'clock, equals 29 minutes before 1 p.m.  
                                    Page 4
    Then I can test factors up to 2^16.5 = 
    92,681: 
     
    S = 2^26, S = 2^52, S=2^104, S = 2^208, S = 
    2^416 x16 = 2^420. 
    Calculate (2^420 - 9) mod p. 
      If RESULT = 0, then p is a factor of 
    2^210-3 or of 2^210+3. 
     
    BUT I did not find any factors up to 92681.  
    (The calculation takes 14 mins, by BBC- Basic 
    2 program "2^420", 20.7.91.  BBC-B micro.) 
     
     
    There is a Test for Primality. 
     
    1)  If a is a positive integer, and p a 
    prime, 
    THEN  a^p == a mod p,   Fermat's theorem. 
     
    So, If we calculate a^p and it does not equal 
    (a mod p), then this theorem tells us that p 
    CANNOT BE PRIME. 
     
    1a)  The Converse is not true.  There are 
    some numbers called Pseudo-primes and 
    Carmichael Numbers, p, which are NOT prime;  
    However, a^p == a mod p, holds for these 
    numbers also, (is true.) 
    N.B.  p is STILL NOT PRIME. 
    (Ref. David Wells) 
     
    2) A stronger test, the Lucas Test, can prove 
    a (large) number definitely is prime. (Ref.  
    Science, 25 AUG 1989,  Beiler, Recreations in 
    the Theory of numbers.  Rosen, 1988. GH Hardy 
    and E M Wright, Introduction to the Theory of 
    Numbers, 5 edn, 1979, Oxford Univ. Press.  
    Standard reference. etc.) 
     
    I have programmed a test like Fermat's 
    theorem for calculating on the BBC model B 
    microcomputer.  My calculations showed that 
    2^210+3 is Composite (check ?). 
     
    Therefore, 2^210+3 could have as many as 12 
    factors, or less, all greater than  92681.  
    This makes the factors TOO BIG to be handled 
    normally with BBC 4-byte integers, and there 
    is considerable territory to test for the 
    actual factors. 
     
    BBC BASIC2 Program "2^420" is approximately 
    16 lines.  Can it be converted to FORTRAN 
    77?,- requires LONG INTEGERS and MOD function 
    up to 1E12.  A computer that provides a MOD 
    function up to one million million may be the 
                                    Page 5
    Hewlett Packard HP 9845 A and B, c. 1983. 
     
     
    BBC BASIC2 Program "A2N+M" , by D S McDonald, 
     (Wellington), can calculate 
    2^(2^210+3) == -0.0168 x p mod (2^210+3) # 2, 
    in about 4.4 mins. on BBC model-B micro.  It 
    requires long multiplication of integer 
    arrays, to Base 2^12 = 4096.  The numbers are 
    calculated exactly by using the clock 
    (modular) arithmetic.   
     
    The numbers involved are greater than BASIC 
    integers (2^31), or BASIC Reals, (2^127), or 
    even numbers that can be stored in a $-string 
    of ASCII characters,  (maximum 255 ASCII 
    characters. - Each character of a string can 
    also have 256 different values, 0-255) 
     
     
    References. 
      Malcolm E Lines, "Think of a number", book. 
    (includes chapter(s), Clock arithmetic : An 
    invention of the Master -- Gauss) 
     
    David Wells, Penguin Dictionary of Curious 
    and Interesting Numbers, reprinted 1987. 

[revised edn 1997.]

    Dominion, 18.9.89.  "New highest prime no." 
     
    Evening Post, 21.9.89.  "Prime no." 
    27.3.92, "Big prime number discovered." 
     M(756,839), Perfect No.,( D. McDonald: not a 
    twin prime.) 
     
    Ivars Peterson, "The mathematical tourist : 
    snapshots in modern mathematics", 1988. 
    Publishing Bibliographical details ?? 
     
     "Factoring Googols" (finding factors of 
    numbers of about 100 decimal digits).  
    Scientific American, December 1988.  (I thank 
    Alex Carr, BBC Acorn User Group NZ, for 
    giving me a photocopy of this reference.) 
     
    Scientific American, December 1988, same 
    issue, Mathematical games - sluicing for 
    prime numbers. Dewdeney  
     
    Scientific American. 247 No. 6:122-130. 
    December, 1982.  The Search for Prime 
    numbers. Carl Pomerance. Arithmetic wheel. 
     
    Albert Beiler, Recreations in the Theory of 
    Numbers, the Queen of Sciences entertains, 
    Dover, 1964. 
     
                                    Page 6
    Science, 25 AUGUST, 1989. Math team vaults 
    over prime record.  Is it prime? 
     
    JW (James William) Bruce, PJ Giblin, PJ 
    Rippon. Microcomputers and Mathematics. 
    Cambridge University Press, 1990.  Includes 
    BASIC programs, primality tests, Ulam 
    diagram, long division algorithm, and 
    calculate pi. 
     
    Rosen, Kenneth HJ.  Elementary number theory 
    and its applications.  Reprinted with 
    corrections, July 1988. Bell Telephone 
    Laboratory.  Addison Wesley..  
    (Pseudoprimes.) 
     
    ORE, Oystein.  Number Theory and its History. 
    McGraw-Hill, 1948. 
     
    GH Hardy and EM Wright. Introduction to the 
    Theory of Numbers. 5th edition, O.U.P., 1979. 
     
    Don S  McDonald, BEEBLET magazine, Calculate 
    primes up to 5.3 million, March 1991. 
     
    C Stanley Ogilvy,  ?  J  ??  ANDERSON.  
    Excursions in Theory of ??  Number Thy. 
     
    NATURE (Journal, England- U.K. - U.S.A.) John 
    Maddox (Editor) News, 26.3.92, "The endless 
    search for primality."  Harwell Laboratory 
    and Cray Research, Mersenne, Lucas-Lehmer, 
    Vallee Poussin Prime No. Theorem ?? Formula, 
    n / ln n.  Neighbours.  M756839. 
     
    D S McDonald, submission FAX/ Letter to 
    NATURE.  "Neighbours of Harwell Prime.", 
    21.4.92. 
     
    D S McDonald.  Results from Fermat's Theorem. 
     Pseudo-primes.  Communicated to Dr John 
    Harper, DSc, Victoria University of 
    Wellington (Mathematics), and Andrew I 
    Macfarlane, Auckland,  Cf Rosen, 1988, 
    Mersenne. 

