All Fermat numbers are squarefree (and more)

MAIN PAGE

All Fermat and Mersenne numbers are squarefree.
A proof based on the order of the subgroup of the powers of 2 modulo F_k or M_p.

by

Jacques BASALDÚA

I M P O R T A N T N O T E

An exception was found for 4.2 of this proof, click here.

                                                                                  C O N T E N T S

    1. Background

    2. Top level proof

    3. Proving ß(F_k) = 2^k+1 and ß(M_p) = p

    4. Proving ß(n) = LCM(a^i-1·ß(a), b^j-1·ß(b), c^k-1·ß(c), .. )

    5. Conclusion

Jacques Basaldúa (c) 2001
All Rights Reserved

This article may be reproduced unmodified either in printed or online journals or websites, except
in websites who charge downloading fees or otherwise limit free and universal access to scientific material.
Printed media may only charge their regular fees.

Please, append the URL www.dybot.com/numbers/sqfree.htm to any reference to it.

Depósito Legal GC-6519/01
Este artículo fue registrado en el Registro de la Propiedad Intelectual de Las Palmas de Gran Canaria, España, el 14 de diciembre de 2001.

1. BACKGROUND

Definition: A Fermat number F_k is the number obtained by replacing k by any positive integer in F_k= ₂2^k₊₁.

    1.1. F_k was conjectured to be prime for any k by Pierre de Fermat (1601-1665).

    1.2. For k in range 0 to 4, F_k is (3, 5, 17, 257, 65537) which are indeed prime. In fact, those are the only known prime values of F_k.

    1.3. The complete factorization of all numbers from F₅ to F₁₁ (both included) is known. Much higher values of F_k have been proved to be composed. Many prime factors of Fermat numbers (even as big as F₂₃₄₇₁), are known. (see http://www.prothsearch.net/fermat.html )

    1.4. All Fermat numbers are relatively prime. In fact, the even more restrictive condition ß(F_k) = ß(any prime factor of F_k) = 2^k+1 where ß is the order of the subgroup of the powers of 2 modulo F_k is proved in http://www.dybot.com/numbers/crab.htm

    1.5. The major open question about Fermat numbers is often exposed as: "Are there finitely many prime values of F_k?"

    This seems extremely likely, but only probabilistic arguments have been exposed. Since Fermat numbers are the "least random numbers of all numbers" (a sequence of 0s limited by two 1s), the weight of such arguments has to be considered prudentially.

    Many authors propose the stricter conjecture "Are all Fermat numbers for k>4 composed?"

    It could even be that:

    No Fermat number has less prime factors than the preceding Fermat number.

    The reduced number of complete factorizations known, (F₀ to F₄ have one prime factor, F₅ to F₈ have two, F₉ has three, F₁₀ has four, F₁₁ has five and F₁₂ has (at least) 7), is way too short to undertake such a risky conjecture. Nevertheless, the amount of known (relatively) small factors of Fermat numbers (without which numbers as big as F₉, not to mention F₁₀ or F₁₁, could not have been factored with current technology) and many special properties of the prime factors of Fermat numbers, such as 1.4, the fact that they are all pseudoprime for base 2 (proved below) and others available at http://www.dybot.com/numbers/crab.htm could point in this direction. It sometimes happens that a more restrictive version of a conjecture leads to a proof easier.

    A similar conjecture is: There are infinitely many composed Fermat numbers. This one is extremely likely, but no proof is known yet.

    One possible way to build a proof could be:

    1. Finding an analyzable expression for ß(5·2^k + 1) as a function of k. This is, of course, the difficult part of the proof. It is not impossible to find such an expression. As you will see below, ß of similar expressions is known.

    2. The values of k = 7, 25, 39, 75, 127, 1847, 3313, 23473, 125413, ... satisfy ß(5·2^k + 1) = 2^j     It can easily be proved:

        a. For all these values of k, 5·2^k + 1 is a factor of the Fermat number (F_j-1).
        b. Considering the size of such numbers and the special form of the factors of Fermat numbers, they are necessarily prime.

    Therefore, solving this problem can be reduced to a proof that ß(5·2^k+ 1) produces infinitely many powers of 2.

    It could almost be enough if it could be proved that there are infinitely many primes of the form 5·2^k + 1, because the primality of 5·2^k + 1 implies Phi(5·2^k + 1) = 5·2^k. (Phi is the Euler Phi function, see 2.1.) Since ß divides Phi and 5·2^k is a prime decomposition, either ß has the factor 5 or Phi/ß has the factor 5. In all cases where Phi/ß has the factor 5, 5·2^k + 1 is the factor of a Fermat number.

    The reason to choose 5 is because there are more known factors of Fermat numbers of the form 5·2ⁿ + 1 than of any other integer. Of course, if another small number makes the analysis easier, it can be used instead. (3 is valid for k = 41, 209, 157169, 213321, 303093, 382449, ... ) The source of this information is the list of factors mentioned above.

    Of course, being able to prove that there are infinitely many composed Fermat numbers would not affect the (more interesting) problem about prime Fermat numbers. Only proving the inverse, i.e., there are finitely many composed F_k, would prove that there are infinitely many prime F_k and this is against all evidence on the subject.

Definition: A Mersenne number M_p is the number obtained by replacing p by any prime number in M_p= 2^p-1

    1.6. Mersenne numbers were described and studied by Marin Mersenne in 1644.

    1.7. Some Mersenne numbers are prime 2, 7, 31, 127, 8191, 131071, 524287, ... and some are not 2047, 8388607, 536870911, ...

    1.8. The biggest known Mersenne prime is M_13466917 and has 4053946 decimal digits. It was found recently by the GIMPS (Great Internet Mersenne Prime Search) initiative (see http://www.mersenne.org) and it is also the biggest known prime of any kind.

    1.9. All Mersenne numbers are relatively prime. In fact, the even more restrictive condition ß(M_p) = ß(any prime factor of M_p) = p where ß is the order of the subgroup of the powers of 2 modulo M_p is a trivial consequence of:
        a. The fact that ß(2^p-1) = p (Proved below in 3.)
        b. That p is prime (definition of Mersenne number)
        c. ß(n) = LCM(a^i-1·ß(a), b^j-1·ß(b), c^k-1·ß(c), ... ) (Proved below in 4.) where n = aⁱ·b^j·c^k· ... is the prime decomposition of n.

    1.10 Similarly to Fermat Numbers, the question of the infinity of composed Mersenne numbers and Mersenne primes is open. It could very well be that:

        There are infinitely many Mersenne primes and there are infinitely many composed Mersenne numbers.

    Until the moment, only 39 Mersenne primes are known but, unlike the 5 Fermat primes which are consecutive, Mersenne primes are mixed among Mersenne composed numbers.

Definition: A squarefree number is a number that is not divided by any square. I.e., all the prime factors of its prime decomposition have the exponent 1. It is either prime or a product of different primes.

Possible interest of this proof:

    A simple search over the internet shows that there is interest in the subject. Also, some people mentioning these conjectures are authors of epoch making documents, specially about the factoring problem, namely:

    The assertion: All Fermat numbers are squarefree.

    1. Was conjectured by A.K. Lenstra, H.W. Lenstra, M.S Manasse and J.M. Pollard in "The factorization of the ninth Fermat number", 1991, page 3.

     "Similarly, one may speculate that all Fermat numbers are squarefree, with perhaps finitely many exceptions."

    The assertion: All Mersenne numbers are squarefree.

    2. By Chris K. Caldwell at "Mersenne Primes: History, Theorems and Lists"

    "Is every Mersenne number square free? This falls more in the category of an open question ..."

    3. By Stephan Thomas Lavavej at Caltech "Mersenne Primes: Development through History, Ongoing Work, and a New Conjecture" 1999.

    "There are still unproved conjectures and open problems, some of which have existed for millennia. Questions such as "Is the number of Mersenne primes infinite?", "If P is prime, is 2^P - 1 always squarefree?", and even "Are there an infinite number of composite Mersenne numbers with prime exponents?" remain unresolved."

    4. By Guy, R. K. ``Mersenne Primes. Repunits. Fermat Numbers.'' §A3 in Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, pp. 8-13, 1994.

    I had no direct access to this book, but an online document titled "Mersenne Prime" by Nikos Drakos, CBLU, University of Leeds makes the following reference to it: "All known Mersenne numbers M_p with p prime are squarefree. However, Guy (1994) believes that there are M_p which are not squarefree."

    Both assertions together: All Fermat and Mersenne numbers are squarefree.

    5. Are in rank 12 of 26 conjectures (1 is Goldbach's) found at http://primepuzzles.net/conjectures/

    "Conjecture 12. Are Mersenne and Fermat numbers square free ?"
    "Well, nobody knows if the Mersenne numbers (2^{p - 1}, p=prime) or the Fermat numbers are squarefree or not."

Possible utility of this proof:

The positive knowledge that all Fermat numbers are squarefree makes a previous squarefreeness test unnecessary when factoring a Fermat number. Quoting the first document mentioned above, page 8 "At the moment, there are no squarefreeness tests that are essentially faster than factoring." Of course, not all factoring algorithms require a previous squarefreeness test.

Maybe the same applies to Mersenne numbers. Nevertheless, there is apparently more interest in finding big Mersenne primes (about a million digits) than in factoring not-so-big Mersenne numbers. About 250 digits could be feasible if the number has 3 factors and maybe less if it has two. 155 is the biggest RSA module factored, but RSA modules are harder because their factors have equal length. Note that my supposition that Fermat numbers have an increasing number of factors does not apply to Mersenne numbers, and therefore factoring big Fermat numbers (F₁₂ has at least 7 factors) is, according to my conjecture, easier than factoring Mersenne numbers of the same size.

to the top

2. TOP LEVEL PROOF

2.1 Preliminary definitions

    In the following, ß(n) is used to indicate the order of the subgroup of the powers of 2 modulo any positive odd integer n. This means: the smallest exponent ß > 0 that makes 2^ß mod n = 1

    In the following, I will use Pascal style notation for mod as in any high level programming language. Many documents on the subject frequently use a congruence sign and write (mod n) on the right side of the equation. In this much simpler notation, mod is just another binary operator like "+ - · / div" where a div b is the integer division, a mod b = a - b·(a div b) is the remainder of the integer division.

    ß(n) is only defined for odd values of n. Even numbers do no have a ß.

    E.g. What is ß(3)?

        2⁰, 2¹, 2², 2³, ... = 1, 2, 4, 8, ...
        2⁰mod 3, 2¹ mod 3, 2²mod 3, 2³mod 3, ... = 1, 2, 1, 2, ...
        ß(3) = 2, because 2 is the smallest exponent satisfying 2² mod 3 = 1

    A number p is called a unit modulo n, if there exists a number q, satisfying: p·q mod n = 1
    This number q is called the modular inverse of p modulo n.
    The order of the group of units modulo n is defined by Euler's Phi function

      Phi(n) = how many numbers are units modulo n.

            If n is prime, Phi(n) = n-1 because all numbers smaller than n are units, except 0.
            If n is prime, Phi(n^k) = n^k-1·Phi(n).
            If m and n are relatively prime, Phi(n·m) = Phi(n)·Phi(m)

    Since the powers of 2 modulo any odd number n are units modulo n, in application of Lagrange's Theorem, "The order of a subgroup divides the order of the group", the order of the powers of 2 modulo an odd integer n entirely divides the order of the units modulo n. I.e., ß divides Phi.

    Or expressed using modular arithmetic: Phi(n) mod ß(n) = 0

2.2 Lemma: ß(F_k) has no odd prime factor.

This is a trivial consequence of the (already mentioned) expression ß(F_k) = 2^k+1 since 2^k+1 is a prime decomposition. (The expression is proved below in 3.)

2.3 Lemma: ß(any non squarefree number) has at least one odd prime factor.

    This is a consequence of the following expression:

    If a, b, c ... are the prime factors of any odd number n and i, j, k, ... are their corresponding exponents. I.e., the prime decomposition of n is:

    n = aⁱ·b^j·c^k· ...

    ß(n) = LCM(a^i-1·ß(a), b^j-1·ß(b), c^k-1·ß(c), ... )                    (The expression is proved below in 4.)

    Since n is odd, a is odd. Also, if n is non squarefree, a^i-1 is odd and >1 for, at least, one prime factor a. And a^i-1·ß(a) has at least one odd prime factor a. The "classic" method to determine the lowest common multiple LCM of two numbers p and q is to calculate their prime decomposition and multiply non repeated factors. From which it clearly follows that LCM(a^i-1·ß(a), q) has at least one odd factor a for any q.

Proof 1: From both lemmata (2.2 and 2.3) it follows that ß(a non squarefree Fermat number) would simultaneously have and have not odd prime factors, which is impossible, following that non squarefree Fermat numbers do not exist.

Note that this proof could be unnecessary if this paper proved that ß(F_k) = ß(any prime factor of F_k) and replaced it in ß(n) = LCM(a^i-1·ß(a), b^j-1·ß(b), c^k-1·ß(c), ... ). Since proving ß(F_k) = ß(any prime factor of F_k) requires explaining the notion of antisymmetric numbers, which requires some notions about periodic forms, I found it more elegant this way. See http://www.dybot.com/numbers/crab.htm for information on periodic forms and antisymmetric numbers.

2.4 Lemma: ß(2^p-1) = p

    (This expression is proved below in 3.)

    In the case of Mersenne numbers, proving ß(M_p) = ß(any prime factor of M_p) is much easier than in the previous case, since p is prime and ß(M_p) = p.

    If M_p is composed, ß(M_p) = LCM(a^i-1·ß(a), b^j-1·ß(b), c^k-1·ß(c), ... ) = p

    The primality of p implies:

    ß(a) = ß(b) = ß(c) = p    =>   ß(M_p) = ß(any prime factor of M_p)

    Since LCM(a, b) for a =/= b cannot be prime.

    And a^i-1·ß(a) = b^j-1·ß(b) = c^k-1·ß(c) = p also implies:

    Proof 2: i = j = k = 1 -> aⁱ·b^j·c^k = M_pis squarefree, because a^i-1·ß(a) is composed for any i other than 1.
     If ß(a non squarefree Mersenne number) is composed.
     => The exponent (= ß) is composed.
     => If the exponent is composed, the number is not a Mersenne number. (The definition of a Mersenne number is: 2^p - 1 for a prime p.)

    Following that non squarefree Mersenne numbers do not exist.

to the top

3. Proving ß(F_k) = 2^k+1 and ß(M_p) = p

3.1. A digression about the relation between ß and bit patterns.

    Two already mentioned expressions:
        Phi(n) mod ß(n) = 0

    and

        ß(n) = LCM(a^i-1·ß(a), b^j-1·ß(b), c^k-1·ß(c), ... )

    are valid for ß being the order of the powers of any number g (generator) modulo n, not necessarily 2. Of course, if the numeration base is changed, the condition "odd number" should be replaced by "number satisfying GCD(g, n) = 1". This condition is required for the existence of ß, ß (in base 2) is only applicable to odd numbers, ß₁₀ (in base 10) is only applicable to numbers not having 2 or 5 as factors of their prime decomposition.

    I speak of numeration base because ß is the length of the periodic expression 1/n written in binary as explained in http://www.dybot.com/numbers/crab.htm

    Besides these general formulae, there are many others that depend on the numeration base, but do not depend on any arithmetic properties of n such as primality, factors, etc.

    Some of them are:

        ß(2^k - 1) = k
        ß(2^k + 1) = 2k
        ß(2^{2k - 1} + 2^k + 1) = 8k - 4
        ß(2^{3k - 3} + 2^{2k - 1} + 2^k + 1) = 6(k - 1)

    As mentioned, the first two expressions may produce prime values (Mersenne and Fermat primes) the third, 2^{2k - 1} + 2^k + 1, produces prime numbers for k = 2, 3, 6, 10, 15, 79, 82, 142, 190, 499, ... (checked until k=1000). The fourth does not produce primes. (All numbers are multiples of 3)

    Other similar formulae, such as:

     ß(2^2k - 2 + 2^k + 1) = 2(k - 1)(2^{k - 1}+ 1)

    are trivial consequences of the formula proved in 4. (This one is the square of 2^{k - 1}+ 1.)

    Others may be described as bitmaps.

    The complete set of numbers satisfying ß=32 is:

#---------------# = 65537(p) ##--------------## = 196611 #-#-------------#-# = 327685 ####------------#### = 983055 #---#-----------#---# = 1114129 ##--##----------##--## = 3342387 #-#-#-#---------#-#-#-# = 5570645 ########--------######## = 16711935 #-------#-------#-------# = 16843009 ##------##------##------## = 50529027 #-#-----#-#-----#-#-----#-# = 84215045 ####----####----####----#### = 252645135 #---#---#---#---#---#---#---# = 286331153 ##--##--##--##--##--##--##--## = 858993459 #-#-#-#-#-#-#-#-#-#-#-#-#-#-#-# = 1431655765 ################################ = 4294967295

    Where #---------------# is the binary representation of F₄ replacing 1s by # and 0s by -.

    This is valid for any Fermat number (except for the word complete).

    A subset of numbers satisfying ß=64 is:

#-------------------------------# = 4294967297 ##------------------------------## = 12884901891 #-#-----------------------------#-# = 21474836485 ####----------------------------#### = 64424509455 #---#---------------------------#---# = 73014444049 ##--##--------------------------##--## = 219043332147 #-#-#-#-------------------------#-#-#-# = 365072220245 ########------------------------######## = 1095216660735 #-------#-----------------------#-------# = 1103806595329 ##------##----------------------##------## = 3311419785987 #-#-----#-#---------------------#-#-----#-# = 5519032976645 ####----####--------------------####----#### = 16557098929935 #---#---#---#-------------------#---#---#---# = 18764712120593 ##--##--##--##------------------##--##--##--## = 56294136361779 #-#-#-#-#-#-#-#-----------------#-#-#-#-#-#-#-# = 93823560602965 ################----------------################ = 281470681808895 #---------------#---------------#---------------# = 281479271743489 ##--------------##--------------##--------------## = 844437815230467 #-#-------------#-#-------------#-#-------------#-# = 1407396358717445 ####------------####------------####------------#### = 4222189076152335 #---#-----------#---#-----------#---#-----------#---# = 4785147619639313 ##--##----------##--##----------##--##----------##--## = 14355442858917939 #-#-#-#---------#-#-#-#---------#-#-#-#---------#-#-#-# = 23925738098196565 ########--------########--------########--------######## = 71777214294589695 #-------#-------#-------#-------#-------#-------#-------# = 72340172838076673 ##------##------##------##------##------##------##------## = 217020518514230019 #-#-----#-#-----#-#-----#-#-----#-#-----#-#-----#-#-----#-# = 361700864190383365 ####----####----####----####----####----####----####----#### = 1085102592571150095 #---#---#---#---#---#---#---#---#---#---#---#---#---#---#---# = 1229782938247303441 ##--##--##--##--##--##--##--##--##--##--##--##--##--##--##--## = 3689348814741910323 #-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-# = 6148914691236517205 ################################################################ =18446744073709551615

This list is not complete, because F₅ is not prime and its prime factors also satisfy ß=64 as mentioned, and so do their products by any number whose ß = 2, 4, 8, 16 or 32.

From the "picture" formed by these numbers, there is no doubt that some ß relations can be described in terms of patterns.

ß((1 followed by j zeros) repeated k times and ended by 1) = (k+1)·(j+1)

Or, the following "lying-P" shape is contained in all numbers whose ß = 4n + 2.

#-## = #----# = #-###-# = #-#-#-#-# = ########## = #-#-## = #------# = #-#####-# = #-#-#-#-#-#-# = ############## = #-#-#-## = #--------# = #-#######-# = #-#-#-#-#-#-#-#-# = ################## = #-#-#-#-## = #----------# = #-#########-# = #-#-#-#-#-#-#-#-#-#-# = ###################### = #-#-#-#-#-## = #------------# = #-###########-# = #-#-#-#-#-#-#-#-#-#-#-#-# = ########################## = #-#-#-#-#-#-## = #--------------# = #-#############-# = #-#-#-#-#-#-#-#-#-#-#-#-#-#-# = ############################## = #-#-#-#-#-#-#-## = #----------------# = #-###############-# = #-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-# = ################################## = #-#-#-#-#-#-#-#-## = #------------------# = #-#################-# = #-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-# = ###################################### = #-#-#-#-#-#-#-#-#-## = #--------------------# = #-###################-# = #-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-# = ########################################## = ; #-#-#-#-#-#-#-#-#-#-## = #----------------------# = #-#####################-# = #-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-# = ############################################## = #-#-#-#-#-#-#-#-#-#-#-## = #------------------------# = #-#######################-# = #-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-# = ################################################## = #-#-#-#-#-#-#-#-#-#-#-#-## = #--------------------------# = #-#########################-# = #-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-# = ###################################################### = #-#-#-#-#-#-#-#-#-#-#-#-#-## = #----------------------------# = #-###########################-# = #-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-# = ########################################################## = #-#-#-#-#-#-#-#-#-#-#-#-#-#-## = #------------------------------# = #-#############################-# = #-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-# ##############################################################

11(p):10 33 :10 93 :10 341 :10 1023 :10 43(p):14 129 :14 381 :14 5461 :14 16383 :14 171 :18 513 :18 1533 :18 87381 :18 262143 :18 (the list is not complete) 683(p):22 2049 :22 6141 :22 1398101 :22 4194303 :22 (the list is not complete) 2731(p):26 8193 :26 24573 :26 22369621 :26 67108863 :26 10923 :30 32769 :30 98301 :30 357913941 :30 1073741823 :30 (the list is not complete) 43691(p):34 131073 :34 393213 :34 5726623061 :34 17179869183 :34 174763(p):38 524289 :38 1572861 :38 91625968981 :38 274877906943 :38 699051 :42 2097153 :42 6291453 :42 1466015503701 :42 4398046511103 :42 (the list is not complete) 2796203(p):46 8388609 :46 25165821 :46 23456248059221 :46 70368744177663 :46 (the list is not complete) 11184811 :50 33554433 :50 100663293 :50 375299968947541 :50 1125899906842623 :50 (the list is not complete) 44739243 :54 134217729 :54 402653181 :54 6004799503160661 :54 18014398509481983 :54 (the list is not complete) 178956971 :58 536870913 :58 1610612733 :58 96076792050570581 :58 288230376151711743 :58 (the list is not complete) 715827883(p):62 2147483649 :62 6442450941 :62 = 1537228672809129301 :62 = 4611686018427387903 :62

3.2. The proof .

    From all the assertions made in 3.1, the only ones that require to be proved for the purpose of this article are: ß(2^j - 1) = j and ß(2^j + 1) = 2j

    3.2.1. ß(2^j - 1) is the order of the subgroup of the powers of 2 modulo 2^j - 1.

    The first units of the subgroup will be 2⁰, 2¹, 2², ... 2^j-1. The next would be 2^jand, since it is bigger than 2^j - 1, it is 2^j- (2^j - 1) = 1.

    This proves ß(2^j - 1) = j because 2^j mod 2^j - 1 = 1.

ß(M_p) = p is a consequence, because M_p= 2^p - 1

    3.2.2. ß(2^j + 1) is the order of the subgroup of the powers of 2 modulo 2^j + 1

    Since 2^e< 2^j + 1 for any e < j + 1, the first units of the subgroup will be 2⁰, 2¹, 2², ... 2^j.

    Note that 2^j mod 2^j + 1 = -1 mod 2^j + 1

    The "j-est" unit in the subgroup = -1 mod 2^j + 1, the "2j-est" unit = (-1)² mod 2^j + 1 = 1

    This proves 2^2j mod 2^j + 1 = 1.

    ß(2^j + 1) can only be 2j or an integer divisor of 2j. The latter is impossible because the units 1 to j of the subgroup are 2¹, 2², ... 2^jall obviously =/= 1.

ß(2^j + 1) = 2j is proved

Since F_k=₂2^k₊₁and replacing j = 2^k produces ß(F_k) = 2·2^k = 2^k+1

ß(F_k) = 2^k+1 is proved.

to the top

4. PROVING ß(n) = LCM(a^i-1·ß(a), b^j-1·ß(b), c^k-1·ß(c), .. )

4.1. Proving ß(a·b) = LCM(ß(a), ß(b)) if a and b are relatively prime.

Let's start this proof with a simple case. Using the following list of all primes of ß < 65 sorted by ß, appropriate values for a simple example can be found:

number : ß number : ß number : ß

3(p): 2 2089(p):29 4432676798593(p):49 7(p): 3 331(p):30 251(p):50 5(p): 4 2147483647(p):31 4051(p):50 31(p): 5 65537(p):32 103(p):51 127(p): 7 599479(p):33 2143(p):51 17(p): 8 43691(p):34 11119(p):51 73(p): 9 71(p):35 53(p):52 11(p):10 122921(p):35 157(p):52 23(p):11 37(p):36 1613(p):52 89(p):11 109(p):36 6361(p):53 13(p):12 223(p):37 69431(p):53 8191(p):13 616318177(p):37 20394401(p):53 43(p):14 174763(p):38 87211(p):54 151(p):15 79(p):39 881(p):55 257(p):16 121369(p):39 3191(p):55 131071(p):17 61681(p):40 201961(p):55 19(p):18 13367(p):41 15790321(p):56 524287(p):19 164511353(p):41 32377(p):57 41(p):20 5419(p):42 1212847(p):57 337(p):21 431(p):43 59(p):58 683(p):22 9719(p):43 3033169(p):58 47(p):23 2099863(p):43 179951(p):59 178481(p):23 397(p):44 3203431780337(p):59 241(p):24 2113(p):44 61(p):60 601(p):25 631(p):45 1321(p):60 1801(p):25 23311(p):45 2305843009213693951(p):61 2731(p):26 2796203(p):46 715827883(p):62 262657(p):27 2351(p):47 92737(p):63 29(p):28 4513(p):47 649657(p):63 113(p):28 13264529(p):47 641(p):64 233(p):29 97(p):48 6700417(p):64 1103(p):29 673(p):48

    Let's take two values, one composed, 21 (=7·3) => ß(21)=6 and one prime, 73, ß(73) = 9. Both are obviously relatively prime.

    Let's call a = 21, b = 73 and c = 21·73 = 1533

    The units of 2ⁱ mod a are named a_i, and the same for b_i and c_i.

    The units a_i, b_i and c_ican be organized in a table as follows: (The table assumes ß(c) = LCM(ß(a), ß(c)), which we pretend to prove.)

2ⁱ mod a

1

a₁

a₂

a₃

...

a_ß(a)-1

1

a₁

a₂

a₃

...

a_ß(a)-1

1

a₁

a₂

a₃

...

a_ß(a)-1

1

2ⁱ mod b

1

b₁

b₂

b₃

...

...

...

...

b_ß(b)-1

1

b₁

b₂

b₃

...

...

...

...

b_ß(b)-1

1

2ⁱ mod c

1

c₁

c₂

c₃

...

...

...

...

...

...

...

...

...

...

...

...

...

c_ß(c)-1

1

The values of our example are:

2ⁱ mod a	1	2	4	8	16	11	1	2	4	8	16	11	1	2	4	8	16	11	1
2ⁱ mod b	1	2	4	8	16	32	64	55	37	1	2	4	8	16	32	64	55	37	1
2ⁱ mod c	1	2	4	8	16	32	64	128	256	512	1024	515	1030	527	1054	575	1150	767	1

    From: 2^ß(a) mod a = 1 it follows that 2^k·ß(a) mod a = 1 for any k > 1, since it is just a repetition of the same subgroup k times.

    The same for: 2^ß(b) mod b = 1 => 2^k'·ß(b) mod b = 1

    The smallest values of k and k' producing an exponent e simultaneously satisfying 2^e mod a = 1 and 2^e mod b = 1 is 2^{LCM(ß(a), ß(b))} mod a = 1 and 2^{LCM(ß(a), ß(b))}mod b = 1 because this is essentially the definition of Least Common Multiple.

    Replacing x = 2^{LCM(ß(a), ß(b))} - 1 we get: x mod a = 0 and x mod b = 0.

    This means, a and b both divide x. Since a and b are relatively prime, we can decompose x as x = a·b·r.

    Therefore: x/a = b·r, x/b = a·r and x/a·b = r. => a·b also divides x.

    x mod a·b = 0 => 2^{LCM(ß(a),
ß(b))} mod a·b = 1
    and, as mentioned, no smaller value produces two simultaneous 1s in 2ⁱ mod a and 2ⁱ mod b

            => ß(a·b) = LCM(ß(a), ß(b)) if a and b are relatively prime. (Partial proof 4.1)

4.2. Proving ß(pⁿ) = p^{n - 1}·ß(p) (for any prime p).

Let's illustrate it with one example using p = 3 and n = 1, 2, 3

2ⁱ mod 3	1	2	1	2	1	2	1	2	1	2	1	2	1	2	1	2	1	2	1
2ⁱ mod 9	1	2	4	8	7	5	1	2	4	8	7	5	1	2	4	8	7	5	1
2ⁱ mod 27	1	2	4	8	16	5	10	20	13	26	25	23	19	11	22	17	7	14	1

    The expression of Euler's Phi function for the power of a prime is Phi(pⁿ) = p^{n - 1}·Phi(p)
    Also, according to Lagrange's theorem, ß divides Phi.

    Defining q_n= Phi(pⁿ)/ß(pⁿ), Phi can be expressed as: Phi(pⁿ) = p^{n - 1}·q_o·ß(p)

    and ß(pⁿ) = p^{n - 1}·ß(p)·(q_o/q_n)

    Therefore, proving ß(pⁿ) = p^{n - 1}·ß(p) is the same as proving q_o/q_n= 1 for any n.

    To understand the meaning of q_n let's use one example. Take a prime p whose ß(p) < Phi(p), e.g.. 31. ß(31) = 5, Phi(31) = 30, q_o= 6. Let's display all the units mod 31 in a ß x q_o (5 x 6) rectangular table as follows.

2ⁱ mod 31

1

2

4

8

16

r₁·2ⁱ mod 31

3

6

12

24

17

r₂·2ⁱ mod 31

5

10

20

9

18

r₃·2ⁱ mod 31

7

14

28

25

19

r₄·2ⁱ mod 31

11

22

13

26

21

r₅·2ⁱ mod 31

15

30

29

27

23

r₁ .. r₅ are (3,5,7,11,15) the smallest units modulo 31 not already in the table while the table is being built from top to bottom. (Any unit not already in the table would be as good, it doesn't need to be the smallest.) It is clear that r_j·2ⁱ mod p is a subgroup of the group of units modulo p, which implies: If the first element is not already in the table, the whole subgroup is not already in the table. It is also clear that the length of these subgroups is ß(p) because they are products (mod n) of the first row by r_j. This way, we can understand q_o as the number of different subgroups of the form r_j·2ⁱ mod p formed by the units modulo p, from which the first one is just a particular case r_j = 1.

The next case after p (= 31) is p² (= 961). The units mod 961 are:

2ⁱ mod 961	1 , 2 , 4 , 8 , 16 , 32, 64, 128, 256, 512, 63, 126, 252, 504, 47, 94, 188, 376, 752, 543, 125, 250, 500, 39, 78, 156, 312, 624, 287, 574, 187, 374, 748, 535, 109, 218, 436, 872, 783, 605, 249, 498, 35, 70, 140, 280, 560, 159, 318, 636, 311, 622, 283, 566, 171, 342, 684, 407, 814, 667, 373, 746, 531, 101, 202, 404, 808, 655, 349, 698, 435, 870, 779, 597, 233, 466, 932, 903, 845, 729, 497, 33, 66, 132, 264, 528, 95, 190, 380, 760, 559, 157, 314, 628, 295, 590, 219, 438, 876, 791, 621, 281, 562, 163, 326, 652, 343, 686, 411, 822, 683, 405, 810, 659, 357, 714, 467, 934, 907, 853, 745, 529, 97, 194, 388, 776, 591, 221, 442, 884, 807, 653, 345, 690, 419, 838, 715, 469, 938, 915, 869, 777, 593, 225, 450, 900, 839, 717, 473, 946, 931, 901, 841, 721, 481
r₁·2ⁱ mod 961	3 , 6 , 12 , 24 , 48, 96, 192, 384, 768, 575, 189, 378, 756, 551, 141, 282, 564, 167, 334, 668, 375, 750, 539, 117, 234, 468, 936, 911, 861, 761, 561, 161, 322, 644, 327, 654, 347, 694, 427, 854, 747, 533, 105, 210, 420, 840, 719, 477, 954, 947, 933, 905, 849, 737, 513, 65, 130, 260, 520, 79, 158, 316, 632, 303, 606, 251, 502, 43, 86, 172, 344, 688, 415, 830, 699, 437, 874, 787, 613, 265, 530, 99, 198, 396, 792, 623, 285, 570, 179, 358, 716, 471, 942, 923, 885, 809, 657, 353, 706, 451, 902, 843, 725, 489, 17, 34, 68, 136, 272, 544, 127, 254, 508, 55, 110, 220, 440, 880, 799, 637, 313, 626, 291, 582, 203, 406, 812, 663, 365, 730, 499, 37, 74, 148, 296, 592, 223, 446, 892, 823, 685, 409, 818, 675, 389, 778, 595, 229, 458, 916, 871, 781, 601, 241, 482
r₂·2ⁱ mod 961	5 , 10 , 20 , 40, 80, 160, 320, 640, 319, 638, 315, 630, 299, 598, 235, 470, 940, 919, 877, 793, 625, 289, 578, 195, 390, 780, 599, 237, 474, 948, 935, 909, 857, 753, 545, 129, 258, 516, 71, 142, 284, 568, 175, 350, 700, 439, 878, 795, 629, 297, 594, 227, 454, 908, 855, 749, 537, 113, 226, 452, 904, 847, 733, 505, 49, 98, 196, 392, 784, 607, 253, 506, 51, 102, 204, 408, 816, 671, 381, 762, 563, 165, 330, 660, 359, 718, 475, 950, 939, 917, 873, 785, 609, 257, 514, 67, 134, 268, 536, 111, 222, 444, 888, 815, 669, 377, 754, 547, 133, 266, 532, 103, 206, 412, 824, 687, 413, 826, 691, 421, 842, 723, 485, 9 , 18 , 36, 72, 144, 288, 576, 191, 382, 764, 567, 173, 346, 692, 423, 846, 731, 501, 41, 82, 164, 328, 656, 351, 702, 443, 886, 811, 661, 361, 722, 483
r₃·2ⁱ mod 961	7 , 14 , 28 , 56, 112, 224, 448, 896, 831, 701, 441, 882, 803, 645, 329, 658, 355, 710, 459, 918, 875, 789, 617, 273, 546, 131, 262, 524, 87, 174, 348, 696, 431, 862, 763, 565, 169, 338, 676, 391, 782, 603, 245, 490, 19, 38, 76, 152, 304, 608, 255, 510, 59, 118, 236, 472, 944, 927, 893, 825, 689, 417, 834, 707, 453, 906, 851, 741, 521, 81, 162, 324, 648, 335, 670, 379, 758, 555, 149, 298, 596, 231, 462, 924, 887, 813, 665, 369, 738, 515, 69, 138, 276, 552, 143, 286, 572, 183, 366, 732, 503, 45, 90, 180, 360, 720, 479, 958, 955, 949, 937, 913, 865, 769, 577, 193, 386, 772, 583, 205, 410, 820, 679, 397, 794, 627, 293, 586, 211, 422, 844, 727, 493, 25 , 50, 100, 200, 400, 800, 639, 317, 634, 307, 614, 267, 534, 107, 214, 428, 856, 751, 541, 121, 242, 484
r₄·2ⁱ mod 961	11 , 22 , 44, 88, 176, 352, 704, 447, 894, 827, 693, 425, 850, 739, 517, 73, 146, 292, 584, 207, 414, 828, 695, 429, 858, 755, 549, 137, 274, 548, 135, 270, 540, 119, 238, 476, 952, 943, 925, 889, 817, 673, 385, 770, 579, 197, 394, 788, 615, 269, 538, 115, 230, 460, 920, 879, 797, 633, 305, 610, 259, 518, 75, 150, 300, 600, 239, 478, 956, 951, 941, 921, 881, 801, 641, 321, 642, 323, 646, 331, 662, 363, 726, 491, 21, 42, 84, 168, 336, 672, 383, 766, 571, 181, 362, 724, 487, 13, 26, 52, 104, 208, 416, 832, 703, 445, 890, 819, 677, 393, 786, 611, 261, 522, 83, 166, 332, 664, 367, 734, 507, 53, 106, 212, 424, 848, 735, 509, 57, 114, 228, 456, 912, 863, 765, 569, 177, 354, 708, 455, 910, 859, 757, 553, 145, 290, 580, 199, 398, 796, 631, 301, 602, 243, 486
r₅·2ⁱ mod 961	15 , 30 , 60, 120, 240, 480, 960, 959, 957, 953, 945, 929, 897, 833, 705, 449, 898, 835, 709, 457, 914, 867, 773, 585, 209, 418, 836, 711, 461, 922, 883, 805, 649, 337, 674, 387, 774, 587, 213, 426, 852, 743, 525, 89, 178, 356, 712, 463, 926, 891, 821, 681, 401, 802, 643, 325, 650, 339, 678, 395, 790, 619, 277, 554, 147, 294, 588, 215, 430, 860, 759, 557, 153, 306, 612, 263, 526, 91, 182, 364, 728, 495, 29 , 58, 116, 232, 464, 928, 895, 829, 697, 433, 866, 771, 581, 201, 402, 804, 647, 333, 666, 371, 742, 523, 85, 170, 340, 680, 399, 798, 635, 309, 618, 275, 550, 139, 278, 556, 151, 302, 604, 247, 494, 27, 54, 108, 216, 432, 864, 767, 573, 185, 370, 740, 519, 77, 154, 308, 616, 271, 542, 123, 246, 492, 23, 46, 92, 184, 368, 736, 511, 61, 122, 244, 488

    Note that r₁ .. r₅ (3,5,7,11,15) are the same values used before and so are all the other units of the previous subgroups. Units have been colored to ease verification. What we pretend to prove, can clearly be noticed: All distinct subgroups modulo p are distinct subgroups modulo p² and modulo pⁿ.

    A strict proof of this can be made as follows:

    Let u be a unit of a subgroup modulo p generated by some factor r. u = r·2ⁱ mod p. This unit belongs to a subgroup modulo pⁿ generated by the same r, if there is some j satisfying u = r·2^j mod pⁿ for any i in u = r·2ⁱ mod p.

    Replacing s_o= r·2ⁱ div p (integer part of the division r·2ⁱ / p) u = r·2ⁱ mod p can be expressed as u = r·2ⁱ - s_o·p.

    Also u = r·2^j mod pⁿ can be expressed as u = r·2^j- s₁·pⁿ. Which is: u = r·2^j - s₂·p (because p obviously divides pⁿ, s₂ = s₁·(pⁿ/p) = s₁·p^n-1).

    Taking both expressions together: u = r·2^j - s₂·p = r·2ⁱ- s_o·p

    r·2^j = r·2ⁱ - (s_o- s₂)·p since (s_o - s₂)·p mod p = 0      =>    r·2^j = r·2ⁱ(mod p)

    (The underlined equal sign = should be understood as "is congruent with". I couldn't find a better way to draw this symbol in HTML.)

This proves: There is some j satisfying u = r·2^j mod pⁿ for any i in u = r·2ⁱ mod p.
-> Distinct subgroups mod p are converted to distinct subgroups mod pⁿ.
-> q_n= q_o (Number of distinct subgroups mod p = number of distinct subgroups mod pⁿ)
-> q_o/q_n = 1
-> ß(pⁿ) = p^{n - 1}·ß(p) (for any prime p) (Partial proof 4.2)

4.3. Final proof. Combining both partial proofs.

    According to the definition of prime decomposition, any number n can be expressed as:

    n = aⁱ·b^j·c^k· ... where a, b, c ... are all different and prime.

    Applying the formula proved in 4.2. to aⁱ, b^j,c^k, ... since a, b, c, ... are all prime

    ß(aⁱ) = a^{i - 1}·ß(a)
    ß(b^j) = b^{j - 1}·ß(b)
    ß(c^k)= c^{k - 1}·ß(c)
    ...

    Since a, b, c, .. are all different, aⁱ, b^j,c^k, ... are all relatively prime and, therefore, the formula proved in 4.1 can be applied, resulting:

    ß(n) = LCM(ß(aⁱ), ß(b^j), ß(c^k), ...) = LCM(a^i-1·ß(a), b ^j-1·ß(b), c^k-1·ß(c), ... )

    Which is what we pretended to prove.

to the top

5. Conclusion
    The two major claims of this article, this is to say, All Fermat numbers are squarefree and all Mersenne numbers are squarefree are only two of the many consequences of the expression: ß(n) = LCM(a^i-1·ß(a), b^j-1·ß(b), c^k-1·ß(c), ... ). This formula can be applied to many Number Theory issues. It can easily be verified, that before the publication of this article, the question of the squarefreeness of F_k and M_p was open. What cannot be verified easily is if the expression ß(n) = LCM(...) was known or not. The author does not belong to the academic world of his country and his only source of information is the internet. (Advanced american books can be ordered from Spain (about $100 each) but cannot be found on the shelves of a bookshop to check if it contains desired information. Public libraries don't have such books, college libraries are not accessible to the public.) It is not easy to search the web for something you don't know if it exists at all and, much less, how it is named. Any information on precedents of this expression will be welcome at jacques@dybot.com.

    Anyway, no matter who first introduced the expression ß(n) = LCM(a^i-1·ß(a), b^j-1·ß(b), c^k-1·ß(c), ... ), the following consequences, and many more which will surely follow, can be noticed.

    1. The same arguments of the major proofs can be applied to numbers of the form aⁿ ± 1 (called Cunningham numbers). I did not verify this in detail. At least for a=10, it is known that ß₁₀(9) = 1, ß₁₀(99) = 2, ß₁₀(999) = 3, ... since 1/9 = 0.1111..., 1/99 = 0.01010101..., 1/999 = 0.001001001001..., This is: ß₁₀ (10^p-1) = p. (ß₁₀ (n) is the order of the subgroup of the powers of 10 modulo n. Only applicable to numbers n satisfying GCD(10, n) = 1) Before concluding too fast, one must notice that 9 is not squarefree. From which concluding " All numbers of the form 10^p - 1 for p = prime are squarefree and relatively prime" is obviously wrong. But, " All numbers of the form (10^p - 1)/9 for p = prime are squarefree and relatively prime" is true.

    2. If a divides b, ß(a) divides ß(b)

    This leads to a factoring algorithm than can only be applied to numbers of known and small ß, but is faster than any other when ß << n. It requires previous computing of a database of primes of known ß. This could be used in applications where it is required to factor small numbers very fast: Instead of verifying divisibility by all primes < Sqrt(n), if the prime database is sorted by ß, it is possible to check the values matching divisors of ß only, greatly reducing the number of divisibility checks.

    ß can be calculated in hardware by a very simple circuit called a CRAB (Crawling reversible automat body). It can be proved that a crab can compute ß in k·ß clockcycles, where k is a very small constant. Much more complicated circuits (e.g. multiplication) have been implemented in one clockcycle, so it is very possible that ß could either be computed in ß clockcycles or known to be above x in x clockcycles. (see http://www.dybot.com/numbers/crab.htm)

    A not very optimized program computed all primes for ß < 65 in about 20 hours on a 1999 (PII-400) PC.

    It takes 1.5 x 2³² steps to complete this.

        a. 2³² steps for the direct problem. (Numbers 1 to 2³² - 1) computing number -> periodic form.
        b. 2³² /2 steps for the inverse problem. (Numbers 2³²to 2⁶⁴ - 1) computing periodic form -> number, only for odd values of ß, since even values do not contain primes (point 5 of this section).

    A serious "number crunching" project could possibly achieve the ß = 65 to ß = 128 range, but this is still too low to make this algorithm any useful.

    A much more effective way to build such a database is factoring 2^k - 1 for increasing k, since (see next point) its factors include the desired primes. 2⁵¹¹ - 1 was factored using NFS (The Number Field Sieve) by R.M.Huizing at CWI Amsterdam. (Some of these conclusions were noticed after creating the mentioned database, which helped understanding ß and other related issues.) Using this method, the database could be extended to ß around 600. ß=511 is known and so is ß=512 (The factors of F₈).

    3. 2^k- 1 is divided by all primes whose ß = k

    Two facts:

        a. ß(2^k- 1) = k
        b. 2^k - 1 is the biggest number whose ß = k. (ß of a number cannot be smaller than its number of bits.)

    Let's consider the opposite assertion.

    There exist: a number n = 2^k - 1 and a prime number p so that ß(p) = k, satisfying n mod p =/= 0.
    Let's compute ß(n·p). ß(n) = k and ß(p) = k. As p is prime, if it does not divide n, they are relatively prime: -> ß(n·p) = k.

    ß(n·p) = k is incompatible with the fact that n is the biggest number whose ß = k

    4. The smallest number whose ß is a prime or a power of a prime is a prime

    If n was composed, one factor f would satisfy ß(f) divides ß(n).

        a. If ß(n) is prime, this is impossible.
        b. If ß(n) is a power of a prime, the cofactor should satisfy ß(cofactor) = ß(n) which is impossible, if n is the smallest number of the ß.

    5. All primes whose ß is even are smaller than 2^ß/2     This is a consequence of the fact that all primes whose ß is even are antisymmetric. Antisymmetric numbers are numbers whose expression 1/n in binary is a ß/2 long sequence followed by the same sequence inverted. Also, ß of a number (and in this case ß/2), cannot be smaller than the number of bits of the number.

    6. If ß(n) is even and n is not antisymmetric, GCD((2^ß(n)/2mod n) + 1, n) and GCD((2^ß(n)/2 mod n) - 1, n) are nontrivial factors of n.

    This is a JATF (just apply the formula) factoring algorithm. It tends to confirm what this article pretends: Any module of known ß is weak. Most numbers have even ß and most of them are not antisymmetric.

    From a test applied to 507368 numbers (All odd numbers < 1000000 plus all whose ß < 65. A number counts twice if it belongs to both categories.)
    78593 were found to be prime. From the remaining 428775 , 358052 (83.5%) were factored by this method.
    From the total 507368 numbers 469058 (92.4%) have even ß, 38310 have odd.
    From the total 507368 numbers 111006 are antisymmetric, 396362 (78.1%) are not.

    Unfortunately, it can neither be applied to Fermat numbers (all factors are antisymmetric) nor to Mersenne numbers (all factors have prime (= odd) ß).

    Proof: It is obvious that x = 2^ß(n)/2mod n is a square root of 1 mod n.

    What is not so obvious is that it is not trivial. Only two trivial possibilities exist:

      x = 1 Is impossible, since the definition of ß explicitly specifies the smallest number satisfying 2^ß mod n = 1
      x = - 1 implies that n is antisymmetric. (This makes part of the proof that all primes whose ß is even are antisymmetric.)

    A known fact on which most efficient factoring algorithms rely, is:
    Knowing an element x satisfying x² mod n = 1, leads to a non-trivial factorization of n, because GCD(x-1, n) and GCD(x+1, n) are two factors of n. Only one of them needs to be computed, since their product is n. One exception to this is when n is a prime power, but this is not and exception to sentence 6 because all prime powers whose ß is even are antisymmetric.

    7. All divisors of Fermat and Mersenne numbers including themselves are pseudoprimes for base 2.

    A number n is pseudoprime for base p, if p^{n -1} mod n = 1. This means that a (Fermat) primality test of this number using p as a base would not identify n as composed. The number n may be prime or composed.

    Remember: ß(any factor of M_p) = ß(M_p), and ß(any factor of F_k) = ß(F_k)

    The prime factors are not only pseudoprime but prime -> 2^{ß(any factor)} mod the factor = 1
    The numbers themselves are pseudoprime or prime. It is more obvious for Fermat numbers since their "presumed Phi" is ₂2^k and ß is 2^k+1 which divides their "presumed Phi". (Presumed Phi(n) is "Phi(n) presuming n is prime" = n-1)

    The product of any two primes of equal ß is a pseudoprime of base 2 and, presumably, the product of any two primes of equal ß_n is a pseudoprime of base n.

    Sentence 7 is "one of the many" properties of factors of Fermat numbers that suggests an explanation of why they are hard to factor even if their ß is known. As mentioned, the knowledge of ß of a module is usually a "breaking" weakness. Needless to say that the knowledge of ß of a 1024 bit RSA module (the product of two around 150 digit random primes) cannot be dreamed of, even for known prime factors.

to the top

2ⁱ mod a	1	a₁	a₂	a₃	...	a_ß(a)-1	1	a₁	a₂	a₃	...	a_ß(a)-1	1	a₁	a₂	a₃	...	a_ß(a)-1	1
2ⁱ mod b	1	b₁	b₂	b₃	...	...	...	...	b_ß(b)-1	1	b₁	b₂	b₃	...	...	...	...	b_ß(b)-1	1
2ⁱ mod c	1	c₁	c₂	c₃	...	...	...	...	...	...	...	...	...	...	...	...	...	c_ß(c)-1	1

2ⁱ mod 31	1	2	4	8	16
r₁·2ⁱ mod 31	3	6	12	24	17
r₂·2ⁱ mod 31	5	10	20	9	18
r₃·2ⁱ mod 31	7	14	28	25	19
r₄·2ⁱ mod 31	11	22	13	26	21
r₅·2ⁱ mod 31	15	30	29	27	23