An Efficient Factoring Algorithm by Repunit Number Method


Baba Laboratory
Michiro Nasu

Excerpt from theory-edge
Questions:
Propositions:
Definitions:
No.01: 2005-03-03 06:49:24 +0900     A Number Puzzle
No.02: 2005-03-03 14:32:46 +0900     Reply to Richard
No.03: 2005-03-03 14:52:16 +0900     Reply to Max
No.04: 2005-03-03 22:31:46 +0900     Seven Propositions
No.05: 2005-04-04 04:38:16 +0900     Proof of Proposition [8], prime repunits
No.06: 2005-03-05 02:12:15 +0900     False answer to Question (4)
No.07: 2005-03-05 13:53:37 +0900     Reply to Daniele wrt an online book
No.08: 2005-03-05 19:28:51 +0900     Apology to Daniele
No.09: 2005-03-05 19:41:03 +0900     Proposal of a Primitive Algorithm for factoring
No.10: 2005-03-07 01:34:35 +0900     Proposal of a Systematic Method for factoring
No.11: 2005-03-07 22:58:05 +0900     Reply to Richard
No.12: 2005-03-08 06:15:37 +0900     Proof of Proposition [8'], [10] and Proposal [9]
No.13: 2005-03-09 08:32:59 +0900     Analysis of Repunit Table for primality condition
No.14: 2005-03-10 02:48:46 +0900     Reply to Daniele
No.15: 2005-03-10 03:09:22 +0900     Self Answer for the previous mail
No.16: 2005-03-10 04:47:42 +0900     Apology to Daniele
No.17: 2005-03-11 06:10:34 +0900     Reply to Vladmir
No.18: 2005-03-14 07:36:45 +0900     Reply to Richard
No.19: 2005-03.15 12:14:01 +0900     Reply to Daniele's 1st Proposal
No.20: 2005-03.16 12:27:43 +0900     Reply to Daniele's 2nd Proposal
No.21: 2005-03.16 22:58:00 +0900     Reply to Daniele's Answer
No.22: 2005-03.19 01:49:29 +0900     Proof of Proposition [15],[16] and [17]
No.23: 2005-03.20 10:47:59 +0900     Reply to Daniele's 3rd Proposal
No.24: 2005-03.24 12:11:48 +0900     Schoolgirl's Homework Conjecture, [9"] and [18]
No.25: 2005-03.25 16:42:03 +0900     Totient/u-length function graph (chart)
No.26: 2005-03.26 12:47:32 +0900     Proposal of Lemma [19]
No.27: 2005-03.27 18:38:15 +0900     Reply to Daniele, Reinvention of a wheel
No.28: 2005-03.30 13:41:16 +0900     Laglange's Theorem, Proposal P1-P7
No.29: 2005-04.02 13:41:16 +0900     Burton's 1989 Paper on primitive roots
No.30: 2005-04.13 03:14:19 +0900     Prime / Composit Criterions


-------- Original Message No.30 --------
Subject: [theory-edge] The Schoolgirl's Homework Algorithm with No Blind Spot for Primality Test
Date: Tue, 12 Apr 2005 11:05:19  -0700 (PDT)
From: Michiro Nasu <nasukun@yahoo.com>
To: theory-edge@yahoogroups.com

Hi Daniele and all!

We succeeded to make up an algorithm for primality test without blind spot. I wrote a tiny program in UBASIC, and it is doing a good job on my machine with samples from 4 to 20 digits in 10-decimal system. Yet forget all of our terms? That's OK. All of what you need is only the psi numbers. Consider a natural number n on b-base decimal system. A psi number y(b,n) is defined [for numbers b and n mutually prime] as the smallest exponent e such that be=1 mod n. We know that the Euler's totient function f(n) satisfies bf(n)=1 mod n for any b mutually prime to n. Accordingly y(b,n)<=f(n), and it is certified that y(b,n) always divides f(n) [18]. We use the following criterions to decide whether n is prime or composite.

Prime Criterion:
A natural number n is prime iff there exists some base b such that y(b,n) = n-1.

For example, let n=13, then n-1=12=2*2*3, y(2,13)=12 as 212=4096=1 mod 13. For other bases, y(3,13)=3, y(4,13)=6, y(5,13)=4, y(6,13)=12, y(7,13)=12, y(8,13)=4, y(9,13)=3, y(10,13)=6, y(11,13)=12, y(12,13)=2. As you see every psi numbers y are of a (possibly single) composite of factors of n-1. The ratio f(f(n))/f(n)=4/12=0.33333 is a good enough figure for us.

Composite Criterion:
If n is an [odd] composite, then there exists some base b such that factors of the psi number y(b,n) forms a factor of n like the following manner. Suppose y and n have factors like y(b,n)=f1*f2*...*, and n=p1*p2*...*. Then for all factors pi of n, there exists some combination of factors taken from {f1, f2, ...} such that pi = fi1*fi2*...fik + 1.

For example, let n=35 and b=2, then y(2,35)=12 as 212=4096=1 mod 35, and y(2,35) = 12 = 2*2*3 and n = 5*7 = (2*2+1)*(2*3+1). Please look at the line again. I have not encountered a paper citing this, but I believe that it is a fact.

As you notice our algorithm needs a perfect ability of factoring composites. In other words, our algorithm must be a perfect factoring algorithm before being a complete primality test. To perform the first criterion is not so hard provided we can factor the number n-1, which is smaller than n and mostly even. It is sure that for every base b, y(b,n) must be a factor of n-1 and to say empirically we can find such b as y(b,n)=n-1 with probability one in three.

N35.gif (6579 bytes)Only if we can have some set of candidates of a factor of n, then to test them is easy, as just make a GCD of n and the factor candidate, and the second criterion says that a psi number y(b,n) is a treasurer of such possible factors. However here is a problem. In the first criterion, we could infer a psi number from the factors of n-1. But in the second criterion, there is no such material to use, and it is sure to seek a psi number from the bottom is quite a time consuming.

When I had almost abandoned the solution only by the mean of programming, I asked Toramasa Ikeda, a skilled soft and/or hard-ware engineer of SONY corp to design a hard-circuit to compute the Psi numbers, then he told me two things, "There may be some abundance for b<<n, isn't it?", and "How does the differential of your formula go?". With his advice I've drawn a graph (chart) of y=bx mod n for fixed b and n. The figure above is an example of such a function with n=35, b=2 and x in the range 1-70, which seems to be a cyclic function with a cycle y(2,35)=12.

Please compare it with the terribly noisy figure of the totient function y=f(x) and the psi function y=y(b,x) with fixed b at MSG#25. You would agree that it is not impossible to get a residue=1 point in a feasible time in a way or another. Do you think/believe that we can solve a 100 digits number problem on a small machine in a very near future?

Michiro

p.s. Again we are experiencing a difficulty to access the mail-server of our provider. So I'll send this mail through a web-mail service. If you have an interest in the subject please check our Repuit-Page at http://babalabo.blogdns.com/repunit/ .

 

blurulr6.gif (2318 ???)

-------- Original Message No.29 --------
Subject:  [theory-edge] Re: Schoolgirl's Homework Conjecture] babalabo
Date:     Sat Apr 2, 2005 8:51 am
From:     Michiro Nasu nasukun@yahoo.com
To:     Theory-Edge <theory-edge@yahoogroups.com>

Hi Daniele and all!

P5 is a proposal for a definitive primality test. I understand that no known primality test is definitive, while P5 asserts that if y(b,n)=n-1, then n is prime. I found a strong validity study for P5 at http://mathworld.wolfram.com/PrimitiveRoot.html.

Although its description is somewhat obscure, it is sure that the author meant that if n and g are relatively prime and ord(g,n)=f(n), then g is a primitive root of n. We know that the modulo order ord(g,n) is nothing but our y(b,n). So it reads that if y(b,n)=f(n), then b is a primitive root of n. We experimentally certified that this is a firm fact through some observation.

As you see, if this is true, then P5 would follow straight. So the Burton paper in 1989 is very crucial for us. Don't you have or have read the paper? If you could access the paper, so wonderful, as our Congress Library in the capital shut out we laymen from access foreign articles. Further if P5 is true, then Lehmer totient problem is about to be decided, although it might still remain some uncertainty. BTW I wonder/fear if Lehmer Problem is Kelly-Ulam conjecture for Number Theory.

I wrote that P5 is not almighty since P4 states that every repunit is an originator of itself. To show P4 is easy. For example, 1000\111=9...1 => U=9, n=111, and nU/9=999/9=111. This means 111 originates 111. As you see it is simply impossible for the number 3=y(10,111) of digits to be equal with the number 111 minus 1. However don't take it wrong.

It does not mean that for such a prime repunit, P5 does not hold. Let p be a prime repunit p=R(b,y(b,p)) on some b-base, then there must be another base b* such that y(b*,p)=f(p)=p-1. The number of such base b* is f(f(p)), which as we've just learned, is the number of primitive root of p. For example, for p=11, f(p)=10 and f(f(p))=4, while

y(2,11)=10, y(3,11)=5, y(4,11)=5, y(5,11)=5, y(6,11)=10,
y(7,11)=10, y(8,11)=10, y(9,11)=5, y(10,11)=2, y(11,11)=0.

Thus b=2, 6, 7 and 8 are the primitive root of 11. E.g., for b=2, {1,2,4,8,16,32,64,128,256,512,1024}=
{1,2,4,8,5,10,9,7,3,6,1} mod 11, and for b=6,
{1,6,36,216,1296,7776,46656,279936,1679616,10077696,60466176}
={1,6,3,7,9,10,5,8,4,2,1} mod 11, etc... Incidentally,

R(2,10)=1023=11*93=(210-1)/1,
R(6,10)=12093235=11*1099385=(610-1)/5,
R(7,10)=47079208=11*4279928=(710-1)/6,
R(8,10)=153391689=11*13944699=(810-1)/7.

As far as I observed, the ratio f(f(n))/f(n) is about 1/2-1/3. This is not so bad figure to seek a solution, although P5 is of no use for composite numbers. In most cases f(f(n)) divides f(n), but it seems not necessary. Consequently the first half of the statement P6 may not be well-formed yet, and the second half is trivial. So I retract P6 at present. P7 may be worse, but I dont mention it here, as we have to learn a bit more.

However I believe that this approach is not only able to give a definitive solution for primality test but also very prospective for composites factoring. How is the distribution of primitivie root numbers b*. At a glance it is not at all random. Don't you think that we can find a sweet spot to make a decision without try and error.

Michiro

p.s. We are still involved in a great trouble. First I have to re-install the OS once again as my mail client was broken accidently, and second as the result I lost all my stock of in/out mails. Third now I cannot send nor receive mails through the mail server of our provider. It was just unbelievable for me to have heard a voice mail recorded at the telephone number of the office of our provider saying that they are in an unscheduled vacancy until April 7th. It means I cannot expect the mail server to recover at least until Apr. 11. So I would send this post via a web-mail service.


blurulr6.gif (2318 ???)

-------- Original Message No.28 --------
Subject:     [theory-edge] Re: Schoolgirl's Homework Conjecture]
Date:     Wed, 30 Mar 2005 13:41:16 +0900
From:     babalabo <babalabo@aya.or.jp>
To:     Theory-Edge <theory-edge@yahoogroups.com>

Hi Daniele and all!

Our Schoolgirl's Homework Conjecture was determined to be a fact, i.e., for all non-radical numbers n, n originates a repunit number and divides always by(b,n)-1 and the repunit R(b,y(b,n)). I'm so happy as I could solve the homework within a due time. Yesterday I found a strong proof for [18], which states that y(b,n) always divides the totient function f(n). Recall Lagrange's theorem.

Lagrange's Group Theorem:
If G is a finite group and H is a subgroup of G, then the order of elements of H divides the order of G.

Lagrange's theorem is provable by using the concept of left cosets of H in G. It is no hard to see that this theorem implies Fermat's little theorem, Euler's Totient theorem, and the proposition [18]. As you know for any prime p, Zp forms a finite field and Zp* is a cyclic group of order p-1. This corresponds to Fermat's theorem. While a modulo multiplication group Mn is defined as an abelian group of order f(n) which represents Euler's theorem.

We can derive an abelian group of order y(b,n) from our formulation of by(b,n)=1 mod n, which gives a subgroup of said modulo multiplication group of order f(n). Of course the situation may be slightly different. For example we may think that n is a variable, while they may regard it as a constant. Anyway I've returned back to Group Theory starting at Number Theory. I wish Vlad would welcome back us. This recursion is of no wonder as far as Group Theory is build up out of the base of natural numbers.

Let's go onward! The most important device in our invention is the u-length function y(b,n). We now understand y(b,n) is equivalent what they call multiplicative order, or simply modulo order denoted by ordna or On(a), i.e., ordna=y(a,n). Simultaneously our y(b,n) is a sort of extension of the totient function f(n), so it is worthwhile to determine to what extent y(n) is applicable instead of f(n), that is, to determine the working area of y(b,n). The merit of y is that y value is obtainable by just one time division and we need not to factor n as for the totient function f(n). However I take it aside, and would like to go into the depth. Now I propose the following propositions.

P1 If a prime p originates a repunit R(b,k), then k divides p-1.
P2 If a number n originates a repunit R(b,k), then n divides R(b,k).
P3 A repunit R(b,k) is factored into distinct repunits and primes.
P4 A repunit number R(b,k) originates itself on any b-base.
P5 If the u-length y(b,n)=n-1 for a number n, then n is prime.
P6 If y(b,n) is a prime, then f(f(n))=0 mod y(b,n)-1 else R(b,y(b,n)) has repunit factors. This proposition is true even if n is radical.
P7 (1) If n is fundamental, then y(b,n)=0.     
(2) If n has just one non-radical prime factor, then y(b,n) is prime.     
(3) If n has more than one prime factors, then y(b,n) is composite.

P1 is just a paraphrase of [18] and P2 of [9"]. Here I placed them parallel to emphasize a Mebius like flavor between them. I think it relates to the hypothesis P3. P4 emphasizes a peculiarity of repunits numbers. A non-radical number originates a repunit number and numbers which originate the same repunit are in an equivalence relation, hence the relation partitions numbers. I want to know what these equivalence classes are. P5, p6 and p7 are aimed to cut the edge and open the can.

We know that if n is prime, then f=n-1. However the opposite is still left open as it is a part of problem known as Lehmer's Totient Problem, which asks if there exist any composite numbers n such that f(n)|n-1. If such a number exists, then it must be a Carmichael number because y(b,n)|f(n)|n-1, and then bn-1=1 mod n. No such number is known so far. I dare to claim P6 to break through this stalemate, although P6 is not at all almighty, for example this method cannot detect a prime repunit since the y of a repunit number n could never be n-1 by P4.

IMHO the proposition if f(n)=n-1 then n is prime must be proven first. However even if this proposition is proved, it might not give us a definitively efficient algorithm for primality test because to gain the totient function we need a factoring beforehand. Here is the difference as the computation of y is so easy. BTW if y=n-1, then of course f=n-1. Regarding P6, we know that y|f, so it is remarkable to hear y-1|ff from P6. These propositions were obtained mainly through some observation of the repunit factoring table maintained voluntarily.

Michiro


Fermat-Toulouse_statue.gif (9601 ???)p.s. I found out that Fermat was an amateur mathematician! Have you ever seen the statue at his hometown Toulouse named "Fermat and his muse". When you look at this statue in the direct front of Fermat, he looks so serious and full of dignity. However if you look at it a bit off the angle, then he is intimately smiling at his muse.

Some examples for the account of the propositions:

P1 example: {xx,yy,..} is a set of repunit divisors {R(xx),R(yy),..}.
    R6={2,3}*7*13, k=6, originator=7,13, while 7=k+1, 13=2k+1.
    R29=3191*16763*43037*62003*77843839397, k=29, while
        3191=110k+1, 16763=578k+1, 43037=1484k+1,
        62003=2138k+1, 77843839397=2684270324k+1.
P2 example:
    R6=111111/7=15873, 111111/13=8547
    R29=1111..1/3191=3482015390508026045475121
        =1111..1/16763=662835477606103389077797
        =1111..1/43037=258175781562634735486003
        =1111..1/62003=179202798430900296939037
        =1111..1/77843839397=142735908161530363
P3 example:
    R24={2,3,4,6,8,12}*99990001
    R25={5}*21401*25601*182521213001
    R26={2,13}*859*1058313049
P4: n=11, y(10,11)=2, (10^2-1)/9=11
    n=111, y(10,111)=3, (10^3-1)/9=111
    n=1111, y(10,1111)=4, (10^4-1)/9=1111
P5: in the range 2<=n<=600 for 2<=b<=16, no counterexample was found,
    though the smallest Carmichael number is 561. the most curious is
    that for b=a2=4,9,16..., I could detect no primes in this manner.
    for some of smaller Carmichael numbers tested on 10-base:
    n=561, f=320, ff=128, y=16
    n=1105, f=768, ff=256, y=48
    n=15841, f=12960, ff=3456, y=120
    n=29341, f=25920, ff=6912, y= 60
P6 example:
    R239=479*142847911*C228, y-1=238
        n=479, f(479)=478,f(478)=238
        n=142847911, f(f(142847911))=36465408=238*153216
        n=C228, f(f(C288))=...
    R41=83*1231*538987*201763709900322803748657942361, y-1=40
        n=83, f(f(83))=40
        n=1231, f(f(1231))=320=40*8
        n=538987, f(f(538987))= 149760=40*3744
        n=201763709900322803748657942361, f(f(n))=...

blurulr6.gif (2318 ???)

-------- Original Message No.27 --------
Subject: Re: [theory-edge] Re: Schoolgirl's Homework Conjecture
Date: Sun, 27 Mar 2005 18:38:15 +0900
From: babalabo <babalabo@aya.or.jp>
To: theory-edge@yahoogroups.com

Hi Daniele!

Thanks for your response.

first I have to say that your messages are formatted in a nice manner, but as result they are not reported in the daily digests and I have some difficult reading them in parallel.

Sorry, I've just received a yellow card from the referee.

If I understand right you search {x,y,z} triples of nonnegative
numbers such that for given n and b n*z+x=x*by

Yes.

In particular I understand that you defined y(b,n) the smaller y for which such a {x,y,z} pair exists.

Exactly.

It seems also that you need only that x < n, but this is on my opinion not too interesting, as {x,0,0} is a valid triple for each x (also for all x < n), as in this case

n*z+x = n*0+x = x, and x*by = x*b0 = x

If you act none, then x remains as it is.

Note also that {0,y,0} is also a valid triple for each y.

OK.

Possibly you need a triple with a positive y and x,z not both zero.

We need at least z>0.

But in this case, if b is even and n=2, you find no valid triple, as 2*z+x=x*by

OK.

admits only triples with even x and thus x=z=0 or x >= 2 (possible triples are {0,y,0} and {2,y,by-1} for any y). Something similar also happens if b is a multiple of n, at least when n is prime.

We have to exclude normal numbers (y=u-length=0). That is, factors of n must not be totally factors of b.

On my opinion your definitions needs some adjustments.

Thanks. I agree with you.

But do not forget, that the necessity to add exceptions to a rule is often indication for a possible weakness of the rule itself.

We call such numbers as above fundamental numbers. For example, if b=10, then a number n=2p5q,p>=0,q>=0 is fundamental on the base b.

BTW I've found out that basically all of what we had discovered is already known in Number Theory, though some may be relatively recent. So apparently we were inventing a wheel. ^^;

As you see, if we could show that for non-radical numbers, r=1 is a solution, then it is the only one solution as x=1 gives the minimum exponent y. They call the exponent y with residue x=1 the multiplicative order of b modulo n, or alternatively the haupt exponent. That is, by=1 mod n, and y gives the length y of the recursion unit of the reciprocal of n.

In general, if a<n and n are mutually prime, then there exists exactly one number 0<=m<=f(n)-1 such that bm=a mod n, called a general multiplicative order, or alternatively discrete logarithm. Seemingly this notion was out of our reach.

Michiro

 

blurulr6.gif (2318 ???)

-------- Original Message No.26  --------
Subject:     Re: [theory-edge] Schoolgirl's Homework Conjecture
Date:     Sat, 26 Mar 2005 12:47:32 +0900
From:     babalabo <babalabo@aya.or.jp>
To:     theory-edge@yahoogroups.com

Hi Daniele and all!

I wrote,

y(b,n)=0 for all numbers n of the kind called ultra-radical numbers all of which factors are a factor of the base b. For example, on 10-base numbers 2,4,5,8,16,.. have y(10,n)=0.

Sorry. Although ultra-radical numbers are not yet formally defined, in this context I misused the term against a notion in my brain. I meant here fundamental numbers but not ultra-radical numbers. now let's give them a formal definition.

Def: A number n on a b-base system is radical (with the radix b) iff some factor of n is a factor of either b or b-1; otherwise n is non-radical. As well an ultra-radical number is a number such that all of its factors are a factor of either b or b-1, while a fundamental number is a number such that all of its factors are a factor of the base b.

Note: Let F be the set of all fundamental numbers, U be the set of all ultra-radical numbers, and R be the set of all radical numbers, then F < U < R. Let nR be the number class ~R, where the proposition [9"] comes to that for all number n \in nR, by(b,n)-1 is divisible by n. At the URL below, you'll find a list of definitions appeared so far. http://babalabo.blogdns.com/repunit/index.shtml/#Definitions/

According to the above definition, the quote above must be rewritten like: "y(b,n)=0 for all numbers n of the kind called fundamental numbers all of which factors are a factor of the base b. For example, on 10-base numbers n=2,4,5,8,16,.. have y(10,n)=0."

It is almost sure that our recursion type "-" class would be identified with the number class fundamental. We noticed that the notion ultra-radical factor would make the difference between the totient function f(n) and the u-length function y(b,n). Proposition [18] says that y(b,n) always divides f(n). With some observation, we certified a fact that a quotient f(n)/y(b,n) is always an ultra-radical number. For example in 10-base, for n=1,2,...100,

f(n)/y(b,n)={
2,*,*,2,1,*,6,*,5,4,2,1,8,*,1,6,1,*,
2,5,1,8,*,2,6,2,1,8,2,*,10,1,4,12,12,1,4,*,
8,2,2,10,24,1,1,16,1,*,2,4,4,6,20,4,2,1,1,16,
1,2,6,*,8,10,2,2,2,4,2,24,9,12,40,2,10,4,6,*,
6,8,2,4,4,2,2,20,2,24,12,2,4,1,4,32,1,1,30,*},

where * is the case, divisor y(b,n)=0, i.e., the number n is fundamental. In the above list, all numbers appeared as a quotient f/y are ultra-radical, in other words, the number n is a product of only 2, 3 and 5. Especially on 2-base, it is certified that every quotient f/y is a form of 2k. I think that this fact would become some help for us preparing for the proof of proposition [18]. So I raise it here as lemma [19].

[19] For any b-base decimal system, for any number n with y(b,n)>0, the quotient f(n)/y(b,n) is an ultra-radical number on the base b, where f(n) is the Euler's totient function and y(b,n) is the u-length function of n.

Michiro

blurulr6.gif (2318 ???)

-------- Original Message No.25 --------
Subject:     Re: [theory-edge] Schoolgirl's Homework Conjecture
Date:     Fri, 25 Mar 2005 16:42:03 +0900
From:     babalabo <babalabo@aya.or.jp>
To:     theory-edge@yahoogroups.com

Hi Daniele and all!

The totient function f(n), also called Euler's totient function, is defined as the number of integers <=n that are mutually prime to n, while our u-length function y(b,n) is defined as the minimum number of recurrent digits of the inverse 1/n of the number n on b-base decimal system. Proposition [18] states that for any number n>2, y(b,n)>0 divides f(n) on any b-base system. I provided a drawing of the functions in the range 1<n<=100 to see how they look like. Apparently [they are] not at all a simple function, but something like a noisy oscillator output. However you would notice sooner or later that there exists some harmonics/multiplicity comparable to the codes of music. Please listen to the sound of numbers for a while...

psi-graph.gif (16223 ???)

It is easy to see that for every prime p, f(p)=p-1. Consequently every prime (on the brown vertical line) is at the peaks of function f(n). In this sense totient function is preferable to a u-length function for the purpose to distinguish primes. However to calculate a value f(n), you need a total factoring of the number, while a value y(b,n) is computable just by a simple division of at most n times.

y(b,n)=0 for all numbers n of the kind called ultra-radical fundamental numbers all of which factors are a factor of the base b. For example, on 10-base, numbers n= 2,4,5,8,16,.. have y(10,n)=0.

Michiro

Rem: The quotients f(n)/y(10,n) for n=1,2,3,...100 are in a form n:f/y, {
3:2, 6:2, 7:1, 9:6, 11:5, 12:4, 13:2, 14:1, 15:8, 17:1, 18:6, 19:1,
21:2, 22:5, 23:1, 24:8, 26:2, 27:6, 28:2, 29:1, 30:8,
31:2, 33:10, 34:1, 35:4, 36:12, 37:12, 38:1, 39:4,
41:8, 42:2, 43:2, 44:10, 45:24, 46:1, 47:1, 48:16, 49:1,
51:2, 52:4, 53:4, 54:6, 55:20, 56:4, 57:2, 58:1, 59:1, 60:16,
61:1, 62:2, 63:6, 65:8, 66:10, 67:2, 68:2, 69:2, 70:4,
71:2, 72:24, 73:9, 74:12, 75:40, 76:2, 77:10, 78:4, 79:6,
81:6, 82:8, 83:2, 84:4, 85:4, 86:2, 87:2, 88:20, 89:2, 90:24,
91:12, 92:2, 93:4, 94:1, 95:4, 96:32, 97:1, 98:1, 99:30},
while f/y=1 for {14, 19, 23, 29, 34, 38, 46, 47, 49, 58, 59, 61, 94, 97, 98},
and primes f/y=\=1 are {3, 11, 13, 31, 37, 41, 43, 53, 67, 71, 79, 83, 83}.
No remarkable fact is observed between a number n to be a prime and the value f/y of n. 

 

blurulr6.gif (2318 ???)

-------- Original Message No.24 --------
Subject:     [theory-edge] Schoolgirl's Homework Conjecture
Date:     Thu, 24 Mar 2005 12:11:48 +0900
From:     babalabo <babalabo@aya.or.jp>
To:     Theory-Edge <theory-edge@yahoogroups.com>

Hi Daniele and all!

I've still stuck at proposition [9]. Now I understand that it is no easy at all but a bit hard problem. However my confidence for the conjecture is very strong. My estimation of the probability for the conjecture to be true is all about 0.9999999999. So I can bet you whole my life for that.

Fermat's little theorem states that for any prime p, bp-1-1 is divisible by p on any b-base. This theorem is the fundamental of Number Theory. Euler's totient theorem extends it to general number n mutually prime to b stating that bf(n)-1 is divisible by n, where f(n) is the Euler's totient function. Our conjecture [9] is an extension of Euler's theorem along this line. The final form of [9] comes like this.

[9"] Schoolgirl's Homework Conjecture:
Let y(b,n) be the minimum number of recurrent digits in b-base decimal representation of the inverse 1/n of a number n. Then for all natural numbers n>1 mutually prime to b and b-1, by(b,n)-1 is divisible by n, as well the repunit number R(b,y(b,n)) is a multiple of n.

Number Theory is the most matured domain in mathematics and has investigated intensively for a long time since the beginning of human history. So I feel a hesitation if I claim that this is the first discovery by us alone. However I believe that at least our approach is somehow new and worthwhile to pursue. Please inform me if you know anything about this.

As you know in decimal number expression, every rational number has either a fixed length of digits or an infinite recursion. Our investigation is focused to the relation between n and the inverse 1/n. It is easy to see that the length y(b,n) of a recursion unit of 1/n is always smaller than n.

Suppose that we are going to divide 1 by n>1. Since 1 is smaller than n we first multiply 1 by bm so as to 1*bm >n. Then we divide the dividend 1*bm by n and obtain Q=1*bm\n...R, and would continue this process until we find out a remainder R that occurred previously. If a remainder R occurs twice in a dividing process, then R...R steps must be repeated endlessly. However from R<n, it is concluded that the division steps, i.e., the length of a recursion unit shall never be more than n. Thus y(b,n)<n.

Def: Given natural number n>1, there exist nonnegative integers x,y and z such that z=x*by \n...x, that reads n divides x*by, the quotient z, and the remainder x<n, in other words, n*z+x=x*by. Obviously a set of {x,y,z} exists infinitely. So we define u-length function y(b,n) as the minimum such number y, as well recursion unit U(b,n) as the minimum such number z. Accordingly we have n*U(b,n)=r*(by(b,n) -1), where r is the first dividend that eventually appears as the remainder.

We may call this equation the recursion equation but not call it recursion formula because we know that a set of {x,y,z} satisfying the equation does not necessarily appear in an actual dividend-remainder sequence. Indeed the equation holds for any x against given n. For example, given n=21, you easily find out the remainder sequence {1,10,16,13,4,19,1,..}, while u-length function y(10,21)=6, U(10,21)=47619 and r=1. However if you take U=47619*x and r=x, then the equation holds for any x. I need your help!

To fortify the continuity between our conjecture and Euler's theorem, I would like to raise one more proposition [18]. A strange flavor of this proposition comes from the fact that function f(n) is base-independent, while y(b,n) depends on base b. The truth probability of this conjecture is also about 0.999999... Please find a counterexample or show the proof.

[18] For any natural number n>2 on b-base decimal system, the value of u-length function y(b,n)>0 always divides the value of Euler's totient function f(n), i.e., gcd(f(n),y(b,n)) = y(b,n).

Michiro
mailto:babalabo@aya.or.jp
http://babalabo.blogdns.com/repunit/

p.s. For your convenience, here is a VB code for calculating u-length function y and totient function f. PFactor(n) is a function which returns the smallest prime factor of n.

Function Psi(num As Long, b As Long) As Long
Dim RT() As Long
Dim x As Long
Dim q As Long
Dim r As Long
Dim n As Long
ReDim RT(num + 1)
n = num
x = 1
RT(0) = x
For i = 1 To n
    x = x * b
    If x >= n Then
        q = x \ n
        r = x Mod n
        If r = 0 Then
            Psi = 0
            Exit Function
        End If
        For j = 0 To i - 1
            If r = RT(j) Then
                Psi = i - j
                Exit Function
            End If
        Next j
        x = r
    Else
        q = 0
        r = x
    End If
    RT(i) = r
Next i
End Function

Function Phi(num As Long) As Long
Dim p As Long
Dim result As Long
Dim n As Long
n = num
result = n
While n > 1
    p = PFactor(n)
    While n / p = Int(n / p)
        n = n / p
    Wend
    result = result - result / p
Wend
Phi = result
End Function

Rem: The function Phi above is written by Takeuchi, Niigata University,   http://www2.cc.niigata-u.ac.jp/~takeuchi/tbasic/ . His Tiny Basic is available at http://www2.cc.niigata-u.ac.jp/~takeuchi/tbasic/English/index.html .

If you have a question why proposition [9"] is "Schoolgirl's Homework Conjecture", check my first post at http://groups.yahoo.com/group/theory-edge/message/10956.

 

blurulr6.gif (2318 ???)

-------- Original Message No.23 --------
Subject: [theory-edge] Re: Repunits as multiple (was Recurrent Numbers)]]
Date: Sun, 20 Mar 2005 10:47:59 +0900
From: babalabo <babalabo@aya.or.jp>
To: Theory-Edge <theory-edge@yahoogroups.com>

Hi Daniele and all!

I'm very glad to come up to the point to respond your post now.

I can now state following theorem

Given a number a and a number n relatively prime to b, then for all k

ak*f(n)-1 is a multiple of n

where f(k) is the Euler totient function.

OK. Let me paraphrase it.

[9'] In b-base decimal system, for all non-radical numbers n, there exists a repunit number R(b,f(n)) originated from the number n, where f is the Euler totient function.

This is just a reformulation of the Euler Totient Theorem

That's right. This Euler Totient Theorem is still a wonder for me, really a product of supremacy genius as well as Euler's Formula. Euler (1707-1783) wrote 75 volumes of books and papers, a half of which were written for his last seventeen years, when he was completely blind! http://leonhard-euler.biography.ms/

http://mathworld.wolfram.com/EulersTotientTheorem.html

Thanks.

It follows directly that for each odd n not multiple of 5 there
exists an infinite number of repunits multiple of n.

Now I agree with you as we are confirmed by [17].

Note that for a prime p, f(pk) = (p-1)pk-1 and thus my
previous conjecture follows also directly from above theorem.

I think we've cleared almost questions. In my next mail I will try cleansing house a bit and would seek the direction from now on.

Michiro

Rem: In above description Daniele adapts k*f(n) as the power of the base while I only use f(n). This difference is due to the difference of motivation. DGD intends to expand to the extent while my intention is to restrict within the repunits originated by the number n and clarify the critical border.

The number of numbers under n is n-1 and for a prime every number under p is mutually prime, hence f(p)=p-1, while pk is still prime for any other numbers and f augments by pk-1.

blurulr6.gif (2318 ???)

-------- Original Message No.22 --------
Subject:     Re: [theory-edge] Re: Repunits as multiple (was Recurrent Numbers)
Date:     Sat, 19 Mar 2005 01:49:29 +0900
From:     babalabo <babalabo@aya.or.jp>
To:     theory-edge@yahoogroups.com

Hi Daniele and all!

Now I've got a proof of [D3]! at first I will prove a few lemmas. But beforehand I'd like to amend the definition of non-radicals.

Def: A number n is non-radical in b-base decimal system if n is mutually prime to both b and b-1; otherwise n is radical. Hereafter let R(b,u) denote a b-base repunit number of u-length u.

[15] For any b-base decimal system and natural numbers m and n, if n is divisible by m, then R(b,n) is divisible by R(b,m).

Proof of [15]: By the premise n=m*q, and by the definition of repunit number, R(b,n) is a m*q copies of digit 1. We partitioned them into q segments of repunit R(b,m) of u-length m. 

R(b,n)=R(b,m*q) = S[i=0 to n-1] bi
= S[i=0 to q-1] ((bm)i * S[j=0 to m-1] bj
= S[i=0 to q-1] (bm)i * R(b,m)
= R(bm, q)*R(b,m).

Thus if m divides n then R(b,m) divides R(b,n). QED.

Note: [15] is essentially equivalent to [D1], so to say another proof of [D1]. As we did not use prime condition, this proposition holds for any composite. From above we can derive two expressions of a composite repunit, i.e., R(b,n) has two divisors on b-base, either R(b,m) or R(b,q), and for each we have a different expression,

R(b,n) = R(b,m*q) = R(b,m)*R(bm,q) = R(bq,m)*R(b,q).

Now we understand that regarding a repunit R(b,n) as a unary number of string length n, multiplication/division of repunits obeys the rule of ordinary integer multiplication/division assuming that any division do not leave a remainder. It is very important to recognize that these operations are base-independent. That is, the u-length of a repunit number is considered to be some kind of invariant.

[16] For any b-base decimal system and natural numbers m and n, if n is a square of m, i.e., n=m2 then R(b,n) is divided by R(b,m).

Proof of [16]: Similar to the proof of [15],

R(b,n) = S[i=0 to n-1] bi
= S[i=0 to m-1] (bm)i * S[j=0 to m-1] bj
= S[i=0 to m-1] (bm)i * R(b,m)
= R(bm,m) * R(b,m)

Thus R(b,m) divides R(b,n), and the quotient Q=R(b,n)/R(b,m)=R(bm,m).

Note: This is a mere corollary of [15]. I just wanted to see how the quotient would look like, and we've got R(b,m2) = R(b,m)*R(bm,m). This means that a repunit number R(b,m2) of a square m2 is factored asymmetrically into two repunits R(b,m) and R(bm,m) with the same u-length m. Now let's try the next proposition.

Proposition: If a prime p is non-radical in both bases of b and bp-1, then repunit R(b,(p-1)2) is divisible by p2.

Proof: From the above reasoning we know that a b-base repunit R(b,(p-1)2) is to be factored into R(b,p-1) and R(bp-1,p-1). By the premise p is prime and mutually prime to both b and bp-1 base. hence by [10'], p divides both R(b,p-1) and R(bp-1,p-1). qed.

However this proof includes a fatal flaw. Because for the base bp-1 of the second repunit, p always divides bp-1-1. This is what Fermat tells us. In other words, no prime p is non-radical simultaneously on the bases both b and bp-1. Here comes the proposition [D3]. Now you understand why the Daniele's formula is asymmetric.

[17] For a non-radical prime p on b-base, repunit R(b,(p-1)*p) is divisible by p2.

As I wrote at the note for [15], a factoring of a repunit has two varying expressions. In this case, we can divide the repunit R(b,(p-1)*p) either/both by R(b,p-1) or/and R(b,p) like the follows.

R(b,(p-1)*p) = R(b,p-1)*R(bp-1,p) (1)
= R(b,p)*R(bp,p-1) (2)

Let's take the first one. by Fermat's little theorem, R(b,p-1) is divisible by p and by [15], R(b,(p-1)*p) is a multiple of R(b,p-1). All of what we need is to show that the quotient R(b,(p-1)*p) / R(b,p-1) = R(bp-1,p) is divisible again by p. Let's see it. It may be helpful to recall R(b,u)=(bu-1)/(b-1)=S[i=0 to u-1] bi.

R(bp-1,p) = S[i=0 to p-1] (bp-1)i
= S[i=0 to p-1] ((bp-1)i -1 + 1)
= S[i=0 to p-1] ((bp-1)i - 1) + p
= S[i=1 to p-1] (b-1)*R(bp-1, i) + p
= (b-1)*S[i=1 to p-1] R(bp-1, i) + p

The last term above is p and of course a multiple of p; the first term S[i=1 to p-1] R(bp-1,i) would look like in bp-1-base,

111111111...1
+1111111....1
 +111.......1
      :
      :
          +11
           +1
-------------
123.........p-1

Each i-th digit of the sum comes to be (p-i)*(bp-1)i. Further,
S[i=1 to p-1](p-i)*(bp-1)i = p*S[i=1 to p-1](bp-1)i - S[i=1 to p-1]i*(bp-1)i

The first term of the sum fell into a multiple of p. For the second, we can use the technique applied to show that a multiple of 3 has a digit sum divisible by 3.

S[i=1 to p-1] i * (bp-1)i
= S[i=1 to p-1] (i * (bp-1)i - 1) + i)
= S[i=1 to p-1] i * ((bi)p-1 - 1) + S[i=1 to p-1] i

By Fermat's ((bi)p-1-1) in the first term is a multiple of p. For the second term, S[i=1 to p-1]i = (p-1)*p/2. thus R(b,(p-1)*p) is divisible by p, and then R(b,(p-1)*p) is a multiple of p2. QED.

Note: It is easy to extend this result to general formula in [D3]. Now we clearly understood that for all number n there exist infinite number of repunits multiple of n provided you dont care which is the base. Even if you are sensitive to the base b, it is sure that there exist infinite number of repunits that is multiple to n only if n is non-radical on b. Supposedly we finally settled our proposition [9] problem, and here I declare that [9] is established as a theorem after that [D3] is able to be proven with no reservation.

Michiro


p.s. Klaus: Thanks for your help. Just the best timing for you to send me a small tool written in Smalltalk on Squeak environment. If I haven't it, I may be still stuck around the point. \(^^)/

Readers: A much more readable and well formed page for this thread is here http://babalabo.blogdns.com/repunit. It is a single web page containing tables of definitions, propositions and questions. Updated daily base along the progress of the discussion.

blurulr6.gif (2318 ???)

-------- Original Message No.21 --------
Subject:     Re: [theory-edge] Re: Repunits as multiple (was Recurrent Numbers)
Date:     Wed, 16 Mar 2005 22:58:00 +0900
From:     babalabo <babalabo@aya.or.jp>
To:     theory-edge@yahoogroups.com

Hi Daniele!

Thanks for your answer.

just a short proof to the last question.

111 is obviously multiple of 3.

Yes.

1001001 is also a multiple or 3 (digits sums up to a multiple of 3).

Very good. I learned this when I was an elementary schoolboy from a famous book (in Japanese) by Centro Yano. Let's recall it.

Proposition: Given b-base decimal number system, and let f be a factor of b-1. Then a number n is divisible by f iff the sum of each digits of n is divisible by f.

Proof: Suppose b-base representation of n = S[i=0 to m]ai*bi. Rewrite the right side as

n = S[i=1 to m]ai*(bi-1)+S[i=0 to m]ai.

As you know (bk-1) is always divisible by (b-1), hence by premise divisible by f. Consequently n mod f = S[i=0 to m]ai mod f. QED.

111*1001001 = 111111111 and is multiple of 32.

1000000001000000001 is again multiple of 3 and multiplying it with 111111111 you get a number with 27 ones that is surely multiple of 33. you can continue at libitum.

OK. Now we understand that at least for some b-base system and a factor f of b-1, [D3] holds. That is, for all primes p, there exists some b>p such that p divides b-1 and satisfies the following,

(b(p-1)*p^k)-1)/(b-1) = 0 mod pk+1.

Can't you generalize this? Perhaps all of what you need to prove is that for any b-base system a number n of form 100...0100....0100...1 is divisible by n, where the recursion part 100...0 is of length n and the number of the recurrence is also n. It seems to me no hard...

m.n.

blurulr6.gif (2318 ???)

-------- Original Message No.20 --------
Subject:     [theory-edge] Re: Fwd: Re: Repunits as multiple (was Recurrent Numbers)
Date:     Wed, 16 Mar 2005 12:27:43 +0900
From:     babalabo <babalabo@aya.or.jp>
To:     Theory-Edge <theory-edge@yahoogroups.com>

Hi Daniele!

I think I have found that for a prime number p, the repunit

(10(p-1)*p^k-1)/9

is multiple of pk+1.

I think affirm that this assertion is likely to be true. Perhaps you inferred this from your observation w.r.t. 3k which I asked you a hint. A repunit number has a form 111...11 and this form is very resemble to what they call unary representation of numbers in complexity theory. Usually a unary number n takes a form of string "000...00" of its length n. So it is quite natural to regard our repunit number as a kind of unary numbers and expect an arithmetic relation on it.

In general a repunit number Rn is defined as Rn=(bn-1)/(b-1). The power n represents the length of the repunit. So we will call it a repunit length or shortly u-length. For the above formula, u-length u=(p-1)*pk. Obviously/surprisingly a repunit length is base-independent. So the above assertion must hold for any base. Readers may think that it is almost unlikely, but if you understand what's Fermat's theorem all about, then you may accept it. For example Fermat says that for all primes [with some exception], for any base a repunit of length p-1 is divisible by p. Let's make a sampling test for p=11 case.

R2(10)=1111111111(2-base)=1023, 1023/11=93
R8(10)=1111111111(8-base)=153391689, 153391689/11=13944699
R10(10)=1111111111(10-base)=1111111111, 1111111111/11=101010101
R16(10)=1111111111=(16-base)=73300775185, 73300775185/11=6663706835

As you see above, regardless the base of the system, repunit numbers of the same length are divisible by the same prime 11, where Rb(u) denotes a b-base repunit number of length u. That is, Fermat's theorem is a very strong support for Daniele's formula, conversely that is an ultimately wide expansion of the Fermat's theorem. Now let's the formula identify [D3]. I expect the assertion [D3] to be proven not in an algebraic direction, rather by an arithmetic/operational way.

For the cases cited in the previous mail I found out that (10294-1) is multiple of 73 and (10272-1) is multiple of 172.

294=2*3*72 and 272=24*17. 7 is a prime which originates R6. Hence 294 is accountable by [D3]. that is, u(p)=6 and u(p3)=6*72. Also the latter comes to like: 17 has a repunit R16, hence u(p)=16 and u(p2)=16*171.

Proving this would imply your theorem 9, i.e. that for each odd number q not multiple of 5 there are infinite many repunits multiple of q.

Now let's define a name for a prime/a factor which is mutually prime to the base. We will call such a prime non-radical prime or non-radical factor. On the other hand, such numbers as 2p*5q are called radical numbers. It is because a base is also called a radix. We think that the proposition [9] is bi-directionally true. Hence we have to prove,

(1) A repunit number has non-radical factors, but no radical factors.
(2) A non-radical number originates a repunit.
(2.1) A non-radical number is a factor of some repunit.

Of course (2) implies (2.1) and perhaps (1) is provable easily. In fact we already proved Lemma [6] which is 10-base version of (1). I think that it is very critical for [D3] to cover (2.1) because IMHO [D2] barely holds for all the different primes and even with the theorem [D3], it still remains a slight question for the strength of the statement.

Fermat's theorem has two formulas w.r.t. repunit numbers. One is the form of bn-1 and the other is the form of bp-1-1. The former corresponds to our originator things. So if we can relax somewhere of the statements, we may get the whole figure at once. You almost blew up the mist surrounding us, and now we are crossing the [a tight] bridge over the river.

Michiro


blurulr6.gif (2318 ???)

-------- Original Message No.19 --------
Subject:     [theory-edge] Re: Repunits as multiple (was Recurrent Numbers)
Date:     Tue, 15 Mar 2005 12:14:01 +0900
From:     babalabo <babalabo@aya.or.jp>
To:     Theory-Edge <theory-edge@yahoogroups.com>

Hi Daniele!

Sorry for my late response.

Recalling some simple notion from algebra, in every polynomial field, xk-1 is a multiple of x-1. Moreover if k is composite, say of the form p*q*r..., then xk-1 is a multiple of all xp-1, xq-1, xr-1,...

Yes, you are right if I take it straight.

[D1]: Verification,

(1) k=p*q*r... => xk-1 = (xp-1)*A = (xq-1)*B = (xr-1)*C...
(2) Rk is a multiple of each Rp, Rq, Rr....
(3) Further, if Rp, Rq, Rr are mutually prime, then Rk is a multiple of Rp*Rq*Rr...

Note: Here p, q, r.. need not to be a prime.

If p is a prime different from 2 and 10, then as you said by Fermat, 10p-1-1 is a multiple of p.

Exactly, assuming you meant "2 and 5".

Fermat's theorem:
10p-1-1=p*X => for all primes p excluding 2 and 5, there exists a repunit Rp-1 divisible by p.

Combining previous notions, we get easy that for each primes p,q,r,... > 5, there are infinite repunits multiple of p,q,r, ... and each combination of them (p*q, p*r, p*q*r, ...).

[D2]: Verification (modified),

(1) By Fermat's: a repunit Rp'=Rp-1 is divisible by the prime p, where p'=p-1.
(2) Let k be a number such as k=p'*q'*r'*...=(p-1)(q-1)(r-1)....
(3) Then by [D1] there exists a repunit Rk such that Rk is a multiple of each Rp', Rq', Rr'....
(4) Therefore by (1) Rk is a multiple of each p, q, r...
(5) Assume that p, q, r... are distinctive primes, then Rk is a multiple of p*q*r...

Note: At point (5) we assumed that every primes p, q, r,.. are different. While k, p', q', r',.. are always even and of course not prime.

> for example, 1010-1 is a multiple of 11, and also 1020-1, 1030-1, ...

1020-1=(1010-1)*X=R10*10000000001
1030-1=(1010-1)*Y=R10*100000000010000000001
1040-1=(1010-1)*Z=R10*1000000000100000000010000000001

Note: 1020-1 cannot be divided by (1010-1)*(102-1). In this case 20=10*2=(11-1)*(3-1), hence p=11, q=3, and 1020-1 is divisible by 11*3=33. 1030-1 cannot be divided by (1010-1)*(103-1). In this case 30=10*3=(11-1)*(4-1), hence p=11, q=4, but 1030-1 is not divisible by 11*4=44 as 4 is a power of 2 and not a prime. 30=1*30=2*15=3*10=2*3*5 and 1030-1 has at least factors 3, 11 and 31 while 4, 6, and 16 are discarded. Take care that the repunit Rk is divisible by p*q*r*... even if Rk is not divisible by the product Rp,*Rq,*Rr'... provided the primes p, q, r... are all the different.  

This covers your theorems 8 and 10, and a part of theorem 9.

Yes, Fermat's implies [8'] and [10]. [9] claims that for all numbers mutually prime with 2 and 5 are originators of some repunits. [D2] asserts that for all such numbers n without power factors, there exists a repunit number Rk divisible by n. But this does not assure that n originates Rk.

It is not clear if for all prime p there are repunits multiple of all powers of p.

Your concern is reasonable as a power pk of a prime p is considered to be the kind of composites. Conversely, is it always possible to make a repunit which is consist of arbitrary distinct primes?, that is, a repunit which has no power factors?

for example 1042-1 is a multiple of 72, 1022-1 is a multiple of 112 and 1078-1 a multiple of 132. Curiously 42=6*7 and 78=6*13. 1066-1 is also a multiple of 112, but this terminates here, as 17*6=102 and 10102-1 is not even multiple of 17. For the moment I have not found any repunits multiple of 172 and any one multiple of 73.

Note: 7 and 13 originate R6, R2 originates from 11, and R16 from 17, while R42 is divisible by R6=O(7,13), R22 by R2=O(11), R78 by R6=O(13), as well as R66 by R2=O(11) where O(n) denotes a repunit originated from n. Here is a recursion table 2<=n<=50.

Q1: 10102-1=1017*6-1 is not a multiple of 17. Why?

A1: 10102-1 is a multiple of each term 1017-1 and 106-1. but 1017-1 is not a multiple of 17. Fermat says that 1016-1 is a multiple of 17, but 1017-1 is probably not. If you like a repunit of a multiple of 17, rather take 1016*6-1=1096-1.

Q2: It seems that there does not exist a repunit of a multiple of 172.

A2: 17 divides R16=(1016-1)/9. hence 1016*16-1=10256-1 might be divisible by 172. Have you tried it?

Q3: It seems that there does not exist a repunit of a multiple of 73.

A3: 106-1 is divisible by 7. hence 106*6*6-1=10108-1 might be divisible by 73. Have you tried it?

3 is a special case (as 9 is a multiple of 3), but it should be easy to show that (103^k-1)/9 is multiple of 3k, i.e. 111 is multiple of 3, 111111111 is multiple of 9, 11...11 (27 one) is multiple of 27 and so on.

I suppose that you probably use some kind of mathematical induction to raise this proposition. But I can't solve it just now. If you like give me a hint or a solution.

M.N.

blurulr6.gif (2318 ???)

-------- Original Message No.18 --------
Subject: Re: [theory-edge] Re: Recurrent Number
Date: Mon, 14 Mar 2005 07:36:45 +0900
From: babalabo <babalabo@aya.or.jp>
To: theory-edge@yahoogroups.com

Hi Richard and all!

You wrote,

mind for the job is not a repunit. If you can back up a bit, simplify, define the terms you are using, give some concrete, finite examples such that I may more easily understand what you are talking about, then I would be of help to the extent of my ability. At present, unfortunately, your conundrums pale in comparison to my own, but I'm certain that is due only to my miscomprehension. I am

Now I opened a web-page which I call Repunit-Page gathering my posts to this list. It is just a collection of my posts and not a complete summary as it is too early for that, but it is edited somehow to help your comprehension. I built it rather for myself as my mail-client was broken by an accident and everything fell into a mess. It took me a time, but I found some new facts overlooked in past through the task. Anyway please check the link below. I believe you enjoy it.

http://babalabo.blogdns.com/repunit/

Michiro

p.s. I have to write small tool programs again for tests, especially to answer Daniele's proposal. Klaus recommended me to use Smalltalk. I was considering to use an interpreter language and Squeak is a development environment with Smalltalk interpreter. So I challenged it, but found that it is no easy to learn rapidly. Perhaps I'll write down a multi-precision arithmetic in C++ by myself as it is no hard at all. The merit is it allows me to define custom operators.

blurulr6.gif (2318 ???)

-------- Original Message No.17 --------
Subject:     Re: [theory-edge] Re: Repunits as multiple (was Recurrent Numbers)
Date:     Fri, 11 Mar 2005 06:10:34 +0900
From:     babalabo <babalabo@aya.or.jp>
To:     theory-edge@yahoogroups.com

Hi!

as a mathematical visa commercial might go..
"an interesting thm, $x.
an interesting proof of an thm, $y.
a picture of the theorem.. $x^y!!"

A good saying! it may seem that we are just faithfully tracing an old passage established in 18th century. But you would see sooner or later the difference, although it's very subtle and somewhat skewed. I hope this ends in a happy hill climbing...

m.n.

blurulr6.gif (2318 ???)

-------- Original Message No.16 --------
Subject:     Re: [theory-edge] Re: Repunits as multiple (was Recurrent Numbers)
Date:     Thu, 10 Mar 2005 04:47:42 +0900
From:     babalabo <babalabo@aya.or.jp>
To:     theory-edge@yahoogroups.com

Daniele,

Read your proposal, just great! Really a splendid result! What a happy day! Indeed I've not expected this. Do you know that today is my birthday? Thanks so much for your big gift for my day.

But I'll bite it later since as I wrote in my mail to you, currently my teeth is being carious (hard attacked by a virus sent from a person who called him/herself D. Pehoushek) and far from comfortable. My small handcrafted tools were all lost in the mess. I'm considering to absolutely re-install the OS into my computer, and maybe it would take at least a day full. Please give me a time.

Michiro

p.s. I haven't yet digest your assertion at all, but I wonder if the Euler totient function may talk anything around the existence of the pseudoprimes or not.

Hi Michiro,

I can now state following theorem

Given a number a and a number n relatively prime to b, then for all k

a^(k*\phi(n))-1 is a multiple of n

where \phi(k) is the Euler totient function.


This is just a reformulation of the Euler Totient Theorem

http://mathworld.wolfram.com/EulersTotientTheorem.html

It follows directly that for each odd n not multiple of 5 there
exists an infinite number of repunits multiple of n.

Note that for a prime p, \phi(p^k) = (p-1)p^(k-1) and thus my
previous conjecture follows also directly from above theorem
.

Daniele

--- In theory-edge@yahoogroups.com, "dgdegiorgi" <degiorgi@h...> wrote:
Hi Michiro,

I think I have found that for a prime number p, the repunit

(10^((p-1)*p^k)-1)/9

is multiple of p^(k+1).


For the cases cited in the previous mail I found out that (10294-1)
is multiple of 73 and (10272-1) is multiple of 172.

Proving this would imply your theorem 9, i.e. that for each odd
number q not multiple of 5 there are infinite many repunits multiple
of q.

Daniele

blurulr6.gif (2318 ???)

-------- Original Message No.15 --------
Subject:     Re: [theory-edge] Repunits as multiple (was Recurrent Numbers)
Date:     Thu, 10 Mar 2005 03:09:22 +0900
From:     babalabo <babalabo@aya.or.jp>
To:     theory-edge@yahoogroups.com

I'm sorry. Now I understand what you meant.

I wrote,

If I read above correctly, it says that xk-1 takes a form of (xp-1)(xq-1)(xr-1).... But I cannot get it. E.g. suppose k=6=2*3, then it becomes (a6-1)=(a-1)(a+1)(a2-a+1)(a2+1+1). Where I was wrong?

Assign b=a3, then we have a6-1=(b2-1)=(b-1)(b+1)=(a3-1)(a3+1) as well as a6-1=(a2-1)(a4+a2+1). Please laugh my ignorance. m.n.

blurulr6.gif (2318 ???)

-------- Original Message No.14 --------
Subject:     Re: [theory-edge] Repunits as multiple (was Recurrent Numbers)
Date:     Thu, 10 Mar 2005 02:48:46 +0900
From:     babalabo <babalabo@aya.or.jp>
To:     theory-edge@yahoogroups.com

Hi Daniele!

Thanks for you response. However I stumbled at the beginning.

Recalling some simple notion from algebra, in every polynomial field, xk-1 is a multiple of x-1. Moreover if k is composite, say of the form p*q*r..., then xk-1 is a multiple of all xp-1, xq-1, xr-1,...

If I read above correctly, it says that xk-1 takes a form of (xp-1)(xq-1)(xr-1).... But I cannot get it. E.g. suppose k=6=2*3, then it becomes (a6-1)=(a-1)(a+1)(a2-a+1)(a2+1+1). Where I was wrong?

michiro

blurulr6.gif (2318 ???)

-------- Original Message No.13 --------
Subject:     Re: [theory-edge] Re: Recurrent Number
Date:     Wed, 09 Mar 2005 08:32:59 +0900
From:     babalabo <babalabo@aya.or.jp>
To:     theory-edge@yahoogroups.com

Hi Richard and all!

In my previous mail I proved theorem [8']. It may be small but a very important step. While we noticed the difference between our formation and others. Although I haven't yet got the proof of the proposition [9], I'm sure that it is a fact. Proposition [9] says that every number n which has neither 2 nor 5 has a repunit number Rk. If the existence of a repunit is a necessary condition for a number to be a prime, we can detect almost nothing by the repunit criterion. For example 21 is a composite but has a repunit number 111 with recursion unit 037. Anyway go onward groping the darkness. Now we need a name for a number which generates a repunit number Rk.

Def: Suppose a number n and its recursion unit U(n). If nU(n)/9 forms a repunit number Rk, then we say that n is an originator of Rk.

In general originator n of a repunit number Rk is a factor of Rk, but it is not always. For example pseudoprimes 33 is an originator of R2=11 but of course 33 does not divide 11. Similarly a factor n of a repunit Rk is not necessarily an originator of Rk. For example 33 is a factor of R6 but not an originator of R6.

An arbitrary number n is an originator of at most one repunit, while a repunit number Rk possibly has multiple originators. E.g. Repunit number 111 has at least 4 originators 7, 13, 21 and 39. We already know that there exist at least 2 repunits which contains a prime p as its factor, while if a number n is an originator of a repunit Rk, then Rk is the smallest repunit that contains n as a factor.

A pseudoprime of base-10 first appears at n=33, while in our method both 21 and 27 already have repunit numbers. In this point of view our method seems pale before any ordinary method. But it isn't. We don't yet consider other conditions than repunit numbers. Recall Fermat's theorem stating that k divides n-1. let's check it.

n recursion unit U k n p/c
# 3 :3 1 k+2 p
# 7 :14285 7 6 k+1 p
# 9 :1 1 k+8 c
# 11 :09 2 5k+1 p
# 13 :07692 3 6 2k+1 p
# 17 :05882 35294 11764 7 16 k+1 p
# 19 :05263 15789 47368 421 18 k+1 p
# 21 :04761 9 6 3k+3 c
# 23 :04347 82608 69565 21739 13 22 k+1 p
# 27 :037 3 9k+0 c
# 29 :03448 27586 20689 65517 24137 931 28 k+1 p
# 31 :03225 80645 16129 15 2k+1 p
# 37 :027 3 12k+1 p
# 39 :02564 1 6 6k+3 c
# 41 :02439 5 8k+1 p
# 43 :02325 58139 53488 37209 3 21 2k+1 p
# 47 :02127 65957 44680 85106 38297 87234 04255 31914 89361 7 46 k+1 p
# 49 :02040 81632 65306 12244 89795 91836 73469 38775 51 42 k+7 c

OK. Just it works. If n is a prime then it is always n-1=a*k. Consequently we can say that our method is no weaker than Fermat's primality test. Now let's go into the recursion unit itself.

n recursion unit U k n (n,k) (n,9) U\9 p/c
# 3 :3 1 k+2 1 3 0...3 p
# 7 :14285 7 6 k+1 1 1 15873...0 p
# 13 :07692 3 6 2k+1 1 1 8547...0 p
# 21 :04761 9 6 3k+3 3 3 5291...0 c
# 33 :03 2 16k+1 1 3 0...3 c
# 39 :02564 1

6

6k+3 3 3 2849...0 c

You may notice the peculiarity of 3 and 33 of which recursion unit is not divisible by 9. This means that n has at least one factor 3. Thus we detect pseudoprime 33 using the knowledge of recurrency in decimals. However our reasoning is still weak for general cases. We need a bit much stronger munitions.

n recursion unit U k Rk\n (n,9) p/c
# 3 :3 1 0...1 3 p
# 7 :14285 7 6 15873...0 1 p
# 9 :1 1 0...1 9 c
# 11 :09 2 1...0 1 p
# 13 :07692 3 6 8547...0 1 p
# 17 :05882 35294 11764 7 16 65359477124183...0 1 p
# 19 :05263 15789 47368 421 18 5847953216374269...0 1 p
# 21 :04761 9 6 5291...0 3 c
# 23 :04347 82608 69565 21739 13 22 48309178743961352657...0 1 p
# 27 :037 3 4...3 9 c
# 29 :03448 27586 20689 65517 24137 931 28 383141762452...348659...0 1 p
# 31 :03225 80645 16129 15 3584229390681...0 1 p
# 33 :03 2 0...11 3 c
# 37 :027 3 3...0 1 p
# 39 :02564 1 6 2849...0 3 c
# 41 :02439 5 271...0 1 p
# 43 :02325 58139 53488 37209 3 21 2583979328165374677...0 1 p
# 47 :02127 65957 44680 85106 38297 87234 04255 31914 89361 7 46 ******...0 1 p
# 49 :02040 81632 65306 12244 89795 91836 73469 38775 51 42 ******...0 1 c

In the table above, 3,9,27 and 33 fails to divide its repunit number Rk, while GCM (n,9)>1 for 3, 9, 21, 27, 33 and 39. These are all composites except 3, especially 33 is a pseudoprime. Accordingly we can say that if a number p is a prime and it is an originator of a repunit Rk, then p must divide Rk. At a glance this condition is weaker than the condition (p,9)=1. However most of pseudoprimes are to be rejected just by this rule. Because it is a remarkable peculiarity that the length k of a recursion unit of a prime is very long, but that of composites especially of pseudoprimes are very short as you see in the table. Hence it usually comes to k << n, and then n cannot divide Rk.

Does there exist anything more? GCM (n,k) may be something. Let's check k=6 case. Here is two primes 7 and 13, and two composites 21 and 39.

n recursion unit U k Rk\n (n,9) (n,k) p/c
# 7 :14285 7 6 15873...0 1 1 p
# 13 :07692 3 6 8547...0 1 1 p
# 21 :04761 9 6 5291...0 3 3 c
# 39 :02564 1 6 2849...0 3 3 c

If n is prime, then n and k are mutually prime. We can detect 21 and 39 as composites by this rule. Maybe this condition is not so significant as we know that it is always k < n and if k not equals n, then it is of course that p is not mutually prime with k as p is supposed to be prime. Now let's summarize the necessary condition of a number p to be a prime,

(1) p has a repunit R_k=pU(p)/9
(2) k divides p-1
(3) for p > 3, (p,9)=1
(4) p divides R_k
(5) p and k are mutually prime

(1) and (2) corresponds to Fermat's theorem. However Fermat's theorem could not develop conditions (3) and (4). Especially rule (4) is strong enough to separate pseudoprimes from prime numbers. But what about the sufficient condition? I wonder if the above conditions are already sufficient for a number n to be a prime.

Michiro


p.s. Allow me a correction: As you see in the above, the table in my mail http://groups.yahoo.com/group/theory-edge/message/10962 was wrong at least at one point.

> 33= 0:30 >> 0:990, correctly:
#33=0:03 >> 0:99

This line reads the number 33 is of #type and the non-recurrent part of 1/33 is 0, recursion unit U(33)=03, and the number has repunit 11. This number is a composite and the first Fermat pseudoprime.

 

blurulr6.gif (2318 ???)

-------- Original Message No.12 --------
Subject:     Re: [theory-edge] Re: Recurrent Number
Date:     Tue, 08 Mar 2005 06:15:37 +0900
From:     babalabo <babalabo@aya.or.jp>
To:     theory-edge@yahoogroups.com

Hi Dick!

Be pleased! I've got the proof for [8']. Recall the Fermat's Theorem.

Fermat's Little Theorem
If p is a prime number and b a natural number, then (1) bp=b mod p. Furthermore, if p does not divide b, then there exists some smallest exponent d such that (2) bd-1=0 mod p, and d divides p-1. Hence (3) bp-1-1=0 mod p.
[8'] Let p be a prime number which is neither 2 nor 5, and the recursion unit of p be U, then pU/9 is a repunit number Rn, i.e., pU=10n-1.

Proof of proposition [8']: By the premise, p and 10 are mutually prime, i.e., p does not divide 10. Hence by Fermat's theorem there exists a smallest exponent n such that 10n-1=0 mod p. This means that p divides 10n-1. Consequently there must be some smallest integer U such that pU=10n-1. We are able to rewrite this equation in a form of integer division A\B=Q...R, that means the quotient of A/B is Q and the remainder is R. Now we obtain in this form, 10n\p=U...1. That is, we divide 10n by p and get the quotient U and the remainder 1. This implies that U is the recursion unit of p. QED.

In factoring practice Fermat's theorem is used for a primality test. I don't know actually what is like their Fermat primality test algorithm, but of course our theorem [8'] is also applicable for the purpose and supposedly our method is much simpler and easier to implement and perhaps faster. Because we need just to divide 1 directly by the number p.

It is a good idea to test every base b < p, and if every expression of pU in each b-base forms a repunit number, then it is almost sure that p is a prime. Regretfully this test is incomplete because it is known that there exist Carmichael numbers (the smallest is 561) that give zero remainder for any choice of the base b a mutually prime to p. BTW a composite which satisfies Fermat's theorem for some b is called a (Fermat) pseudoprime.

The Fermat's theorem is applicable just for prime numbers. however as far as we observe, theorem [8'] is extensible to general composite with #type, ie, numbers which has neither factor 2 nor 5.

[9] Let m be an integer without factor 2 nor 5, and the recursion unit of m be U, then mU/9 is a repunit number Rn, i.e., mU=10n-1.

I wonder if Fermat's Little Theorem is extensible in this manner. Because the proof of theorem [8'] almost owes to Fermat's theorem. But as our test samples are so small, proposition [9] may not be true. Anyway we've succeeded to establish theorem [8'] and as far as I understand it might be quite possible that we discovered the fact for the first time.

Michiro


p.s. The Fermat's theorem contains much more content than we used in the proof above. Let's take a look at equation (3). Now we know that if p is a prime, then 10p-1-1 is also divisible by p. Consequently there exists some integer V satisfying pV=10p-1-1. You may think that this equation is mostly the same with the above. But it is not. Unit U has a condition "smallest", while V does not. surely V never be the recursion unit of p. Needless to say a recursion unit U of any number x is only one. In other words (3) expresses that there exists one more repunit which has factor p other than (2). This is the very prime that we were seeking in the sky.

[10] A prime number p is a factor of at least two repunit numbers such as R* =(10n-1)/9 and R+ =(10p-1-1)/9, where n is the smallest number that satisfies 10n-1=0 mod p, and n divides p-1.

Proof of [10]: almost similar to the proof of [8']. QED.

In general the repunit number R* is relatively small but R+ may become a huge number. This is the real picture that I described as "in the sky". But now we understand that at least there does not exist an orphan prime in the universe. To hear that I'm somewhat relieved. aren't you? The distance between these two primes is surely astronomical, but I believe that we can use this knowledge in any way because only if given number m, we can compute R* and R+ quite easily by just a simplest calculation. In this sense, the distance is not to fear at all.

blurulr6.gif (2318 ???)

-------- Original Message No.11 --------
Date: Mon, 07 Mar 2005 22:58:05 +0900
To: theory-edge@yahoogroups.com
From: babalabo <babalabo@a...>
Subject: Re: [theory-edge] Re: Recurrent Number

Hi!

I'd like to be able to help, but I am not a programmer, I don't know graph theory, your notational conventions and nomenclature are very confusing to me and while I am sure I could figure out where you are coming from, I find myself unmotivated to do so because I spend all of my ultra-precious spare time on my own researches. Your idea of

That's OK. let's take it slow. No hasty travel. To test a narrow range is easy and enough for now. Maybe I can write it in a few days.

using a single number as an encoding reference for factoring is an idea parts of my research are pointing to, but the number I have in mind for the job is not a repunit. If you can back up a bit,

Very interesting!

simplify, define the terms you are using, give some concrete, finite examples such that I may more easily understand what you are talking about, then I would be of help to the extent of my ability. At

I'll write a brief note for the account later.

present, unfortunately, your conundrums pale in comparison to my own, but I'm certain that is due only to my miscomprehension. I am

Our directions are seemingly very close.

presently preparing a paper for publication and it has taken my spare time over a 4 month period just to Tex up 11 pages. I am figuring the final paper will have 30-40 pages, but I may split it up into 2 or 3 papers (which will be more work in the long run actually).

I've never experienced Tex but if it's like that, I may throw it out.

I had looked into some stuff in the arena you are dwelling in very briefly. I take the rational number >1 formed by the ratio of 2 primes, discern the repeating string from the decimal expansion, and repeat the repeating string to the left (backwards) until I obtain the sequence of rational numbers all >1 which remain faithful to the repeating pattern even to the left of the decimal.

OK.

For the very few scant, low numbers I checked, when the original rational number is > 1 and is the ratio of 2 primes, it seems all digits to the right of the decimal are faithful to the repeating string, thus the differences between the original number and each number (>1) of the derived sequence is always an integer. The nature of these integers as dependent on the nature of the numerator and denominator of the original rational number was the particular focus of my interest at the time, but I didn't go very far with it. It is

I'm afraid if the integer part is not so significant. For example, 199/29=6+25/29=6+25*1/29. Consequently at least in my eyes what you are dividing is not a prime but a composite 25=5*5.

on one of my many dozens of back-burners for future investigation, though my current, favored research also involves the decimal expansions of rational numbers in a different way.

I will try to upload a mathematica file to the file area that contains some simple examples of what I have described. Here are a few lines from that file I find particularly interesting because my process applied to the ratio of prime 199 over 29, yields first sequence integer 1 and 199/31 yields -1. When I get back to it, I had planned to try and write a routine to examine other twin primes to see under what circumstances they give 1/-1 like that, and also to find any instances where prime numerators and denominators forming rationals>1 failed to yield integers for the sequence (which I have not yet found).

N[199/29,40]=6.862068965517241379310344827586206896552
6.862068965517241379310344827586206896551724137931034482759`40.
-5.862068965517241379310344827586206896551724137931034482759`40.
1.00000000000000000000000000000000000000

N[199/31,40]=6.419354838709677419354838709677419354839
6.41935483870967741935483870967741935483870967741935483871`40.
-7.41935483870967741935483870967741935483870967741935483871`40.
-1.00000000000000000000000000000000000000

Other examples yield primes and composites alike and no patterns immediately emerge, but I only scratched the surface. Typically, when I research, my spinal column, which knows more truth than my brain proper, will send me signals that what I am looking at is worth

My signals may come up from my stomach...

pursuing. I recall getting those signals at the time I spent a little time on this one, I really do believe there is more to the story here, but I also believe that many, many, many mathematicians have been down this road before, so there must be something out there

Agree.

already. I have already wasted years discovering things that were already discovered, so I choose my battles carefully and try to do the best I can to make sure the war isn't already over before I take

I'm always rambling around the ancient site of theaters listening to the voices of wind talking about their passion, ambition and regrets...

up the fight. If there were any programming skills to be thrown toward this endeavor, I should like a tool with which to generate and examine the properties of my integer sequences and indeed, study which numbers always give rise to integer sequences and those that always give rise to non-integer rational sequences. But even better, would be references to related work that has already been completed.

Today I was going to write a small test program for the conjecture [8'], but could not [complete] as my computer (bombed yesterday) was very bad state and I cannot repair it yet.

Michiro

 

blurulr6.gif (2318 ???)

-------- Original Message No.10 --------
Date: Mon, 07 Mar 2005 01:34:35 +0900
To: theory-edge@yahoogroups.com
From: babalabo <babalabo@a...>
Subject: Re: [theory-edge] Re: Recurrent Number


Hi Richard and all!

I showed a case method for factoring using Repunit Table. I think that it works anyway, but not so good as the search space is relatively too large comparing the fruit to be obtainable. I would like to propose a much more effective method to search factors in a systematic way.

Suppose that we desire to search in a range n <= N, where N is an integer and n is a number of digits of 10-base integers. Let R be the set of repunit numbers from R2 to Rn. We will compose an undirected graph G such that the vertex set of G is R and a pair of nodes, ni and nj are connected iff the corresponding Ri and Rj are mutually prime. Now take an arbitrary pair of non-adjacent nodes ni and nj and get GCM $ij.

If $ij=1, then connect ni and nj with an edge, otherwise divide the node values by $ij and rename the nodes ni and nj to ni/$ij and nj/$ij respectively. Add a new node $ij to G and connect it with all the nodes which were adjacent to either ni or nj. You would continue this procedure until you get a complete graph. Needless to say if you find two nodes with the same value, merge them into a single node. This procedure halts in finite time and the time cost per factor is feasible.

Assume we have an efficient algorithm B to determine if a value is prime or not. Then apply the test program B to the nodes in G and remove every nodes decided to be prime from the graph. If the graph G becomes null, then our job is complete. But it is almost sure that the graph G is not empty. Regretfully we can no longer factor those nodes by only our method because no two nodes ni, nj share individual prime p in the graph.

I don't know how much unfactored nodes would remain there, but could only say that factoring must be an endless job for human. It might be that another prime of the same value is contained in a larger repunit Rn untested. But these numbers are far in the sky. so we are reluctant to call our method Separation of the Sky and the Ground. The worse, there might be no partner even in the sky, i.e., the occurrence of the prime might be just once on the ground, so to say an orphan in the universe.

However if this is the case, we may still have a clue to manage the situation as we know that if a prime p appears in a repunit Rn just once, then the recursion unit U of p must be a factor of Rn. I don't know how can we resolve this formula/cryptograph for now but here is a hope.

To use different/multiple decimal bases simultaneously is a good idea because it is very unlikely that two different systems have the same unfactored node set. I think that the sky and the ground method is very attractive because you can start at just 100*100 GCM computations for a vast 100-digit whole space. Are you satisfied?

Michiro


p.s. In our convention the greatest common divisor is abbreviated as "GCM" but it might be "GCD" else where. Can anyone test the sky and the ground method? As I could only reserve the time bound to this weekend for the subject. (Another excuse: I still haven't a multiple-precision arithmetic.)

But! I've happened to notice a big hall in my argument up to this point. Evidently question Q(4) is not answered/proven yet.

Q(4) Does there exist a prime number p such that p does not divide any repunit number Rn? If yes, then show the minimum one.
A4: No. every prime number p except 2 and 5 appears in a Repunit Table. Let the recurrent unit of p be U and get the product pU. We already know that pU has a form of 999...9 since we assumed that p is a prime and neither 2 nor 5. Thus we obtain a repunit number R=pU/9=111...1 which has a factor p and p shall sit in the table.

I think that it was not "we already know" but "we just know empirically". See http://groups.yahoo.com/group/theory-edge/message/10962 . In other words proposition [5] is not a theorem but an observation/conjecture.

[5] Every recurrent number n of type '#' is a divisor of some number m of length k such as 111...1=(10k-1)/9. As well a recurrent number of type '>' divides a number such as 9999...90.

So at least we need to formally prove the following proposition.

[8'] Let p be a prime number which is neither 2 nor 5, and the recursion unit of p be U, then pU/9 is a repunit number Rn, i.e., pU=10n-1.

However I have a confidence of [8'] to be true and even if it isn't, the sky and the ground method is still valid. If [8'] does not hold, then there might be a prime which is not in any repunit and said to be not so much an orphan as missing/drafting in the universe at all. Anyway the following question is the most essential and crucial.

Q'(4) prove or disprove the proposition [8'].

This is a great chance/challenge for you. Bite it!

 

blurulr6.gif (2318 ???)

-------- Original Message No.9 --------
Subject:     Re: [theory-edge] Re: Recurrent Number
Date:     Sat, 5 Mar 2005 19:41:03 +0900
From:     Baba Labo <babalabo@aya.or.jp>
To:     <theory-edge@yahoogroups.com>

Hi Dick and all!

I wrote,

If this dream comes true, then their effort turns from searching a star in the sky to building a public resource like Human Genome Project. of course I don't think that this is any easy but believe to be possible. You may wonder how are recurrent decimals relevant

Now I found a solution, just a simple one. Assume that we have an efficient algorithm A for computing GCM (Greatest Common Deviser). Then just check our Repunit Table with the algorithm A and find a repunit number Ri which is not mutually prime with the number n. Clearly A gives us a factor x of n. to perform this we need both of

(1) An efficient GCM algorithm A, and
(2) A small enough lookup table R[n].

I believe that we possess the both. It is very good for us that we need not each entry of repunit number of the table to be already factored. The factor x of Ri would be given on the fly. I don't know if this method is actually applicable on the factoring world. But it seems at least for me to be worthwhile to try. If the 10-base repunit table is too sparse for practical purpose, you can adopt 2-base repunit table, i.e., Mersenne Table alternatively. If you are experienced in factoring, please estimate the cost for factoring the smallest unfactored number n in your table with this method. If you think it is not applicable at all, tell me your reason.

Michiro


p.s. It is possible that I accidentally send someone a mail with a file attached. If you receive one, please don't open it and just throw it into your trash bin. As I wrote in my previous mail I received a mail from an old member of this mailing list. A file was attached to the mail and I opened it with the secret key in the mail. It was a warm worm named Win32.Beagle. Fortunately my virus checker killed it in the egg.

However I've received a delivery errmsg from cs.umass.edu. It says that my mail addressed to a person in the host is infected by a virus named W32/Netsky.p@MM. If this causes trouble on you, I apologize you deeply for my carelessness.^^;

 

blurulr6.gif (2318 ???)

-------- Original Message No.8 --------
Subject:     Re: [theory-edge] Re: Recurrent Number
Date:     Sat, 5 Mar 2005 19:28:51 +0900
From:     Baba Labo <babalabo@aya.or.jp>
To:     <theory-edge@yahoogroups.com>

I'm sorry. It was due to my setting of the internet access.

----- Original Message -----
From: "dgdegiorgi" <degiorgi@hispeed.ch>
To: <theory-edge@yahoogroups.com>
Sent: Saturday, March 05, 2005 5:01 PM
Subject: [theory-edge] Re: Recurrent Number

>
>
> Very strange.
>
> Clicking the Link I give, I get a page with a picture of the book
> and a lot of links to the chapters.
>
> The whole book is in
>
> http://www.ams.org/online_bks/conm22/conm22-whole.pdf
>
> (1.4mb)
>
> Daniele
>

blurulr6.gif (2318 ???)

-------- Original Message No.7 --------
Subject:     RE: [theory-edge] Re: Recurrent Number
Date:     Sat, 5 Mar 2005 13:53:37 +0900
From:     babalabo <babalabo@aya.or.jp>
To:     <theory-edge@yahoogroups.com>

Hi Daniele!

Thank you very much for your ever unchangeable kindness.

I have no substantial contribute to the discussion, but some factorizations of bn+1 and bn-1 can be found in a free e-book http://www.ams.org/online_bks/conm22/

It seems that they changed the link to the book. But this works. http://www.ams.org/online_bks/conm22/conm22-chVI.pdf

There are the factorizations of 10n-1 for 1<=n<=150 and of odd n < 330.

Yes, it was my expectation. But actually my downloaded copy has only 2 pages of VI. How to Use the Main Tables, and the main tables themselves are missing. Perhaps they changed their policy because that is a part of their commercial products. Anyway thanks a lot.

BTW this morning I've received a mail from our legend, Dan Pehoushek. Really surprised! but my reply returned for some delivery failure. Dan, are you there? Please bite, no need of hesitation!

Michiro

Rem: The missing link was my mistake. But "Dan" really bit me with less hesitation.

 

blurulr6.gif (2318 ???)

-------- Original Message No.6 --------
Subject:     RE: [theory-edge] Re: Recurrent Number
Date:     Sat, 5 Mar 2005 02:12:15 +0900
From:     babalabo <babalabo@aya.or.jp>
To:     <theory-edge@yahoogroups.com>

Hi Richard!

I'm glad you found the information you were seeking.

Thanks a lot. I've earned a great crop.

You say that as if unfactored 100 digit numbers shouldn't be so

Yes, I was thinking so far.

plentiful. 100 digits primes are easy to find and prove, but factoring a 100 digit number is still very intensive and time consuming.

I've gradually got the situation. The Cunningham Project is a big project for many years spending enormous amount of human power. They are maintaining a large scale of tables to be filled and collaborating through network. An astronomical effort like a planet search project.

I don't think that we have yet enough knowledge of recurrent decimals, I'd like to show you how it could combine to their factoring table. Let's call the table of repunit numbers Repunit Table. As you see this table is a very sparse table, so to say exponentially sparse. If we can use this table as a lookup table for factoring, that will be fine. But beforehand I would prove the question Q(4). just as easy.

Q(4) Does there exist a prime number p such that p does not divide any repunit number Rn? If yes, then show the minimum one.

A(4) No. every prime number p except 2 and 5 appears in a Repunit Table. Let the recurrent recursion unit of p be U and get the product pU. We already know that pU has a form of 999...9 since we assumed that p is a prime and neither 2 nor 5. Thus we obtain a repunit number R=pU/9=111...1 which has a factor p and p shall sit in the table.

How can we use this table for factoring? To make the story simple assume that we have a function F(n) which gives an index value of the table, and each repunit number has its own (not necessarily unique) key. Given composite number n, you can compute the value by F(n), seek the table and find some Rn entries which match to the value. Every Rn is already factored and you will get a bunch of primes to be tested. Once you've found a factor, then you can go on until finish the factoring just repeating this procedure.

If this dream comes true, then their effort turns from searching a star in the sky to building a public resource like Human Genome Project. Of course I don't think that this is any easy but believe to be possible. You may wonder how are recurrent decimals relevant to factoring. But perhaps you've heard somewhere that division is equivalent to multiplication. In fact I told my schoolgirl like that, and it's the point where I began reflecting on it to myself.

Let's take a look at some sample. Let U(n) denote the recurrent recursion unit of number n. then U(3)=3, U(7)=142857, and U(21)=047619, while 142857=47619*3, and we earn U(7)=U(21)*U(3). Regretfully this doesn't work on the other side. But too early to abandon. we are just at the beginning.

Michiro

Rem: Apparently this proof above is incomplete as "we already know just empirically". However we would get a genuine proof later.

blurulr6.gif (2318 ???)

-------- Original Message No.5 --------
Subject:     RE: [theory-edge] Re: Recurrent Number
Date:     Fri, 4 Mar 2005 04:38:16 +0900
From:     babalabo <babalabo@aya.or.jp>
To:     <theory-edge@yahoogroups.com>

Hi!

The number M(k)=111...1 has a name, repunit number, given by Beiler in 1966. http://mathworld.wolfram.com/Repunit.html, thanks Richard. From the naming "repeating-unit", I guessed that he had been considering what we call recursion unit when he named it, but it may be just a unit "1". The factoring table which I proposed in my first mail is maintained on line by Brillhart et al since 1988, which I asked Vlad if the table is useful. BTW repunit number Rn is a special case of Cunningham number bn-1, and R2 corresponds to Mersenne numbers. Now we will use repunit number Rn instead of our M(k) numbers.

Def: repunit number Rn=(10n-1)/(10-1)=(10n-1)/9.

Rem: In general repunit number Rn of b-base system is defined as Rn=(bn-1)/(b-1).

[8] A repunit number Rn can be prime only if n is prime.

Proof of [8]: Assume n is a composite n=ab. Then 10ab-1 is a binomial number and can be factored algebraically. If a is even and a=2m then we get 102mb-1=(10mb-1)(10mb+1). Assume a odd, then

  (10a-1)(10a(b-1)+10a(b-2)...+1)=(10-1)(10a-1+10a-2...+1)(10a(b-1)+10a(b-2)...+1).

Hence Rn cannot be a prime, contradiction. QED.

Another proof of [8]: Assume n is a composite n=ab, then it is easy to see that Ra divides Rn as well as Rb. For example, R12=111111111111 is divisible by R2=11, R3=111, R4=1111 and R6=111111. QED.

Q(3) Repunit number Rn is prime only if n=2 and R2=11.

A(3) No. there exist repunit prime numbers other than 11. We succeeded to factor 18 digits Rn, and the next R19 was the second prime repunit.

Only seven repunit primes are known at present including R2=11, like n=2, 19, 23, 317, 1031, 49081, 86453. Madachy showed R2, R19, R23, R317 in 1979, Brillhart and Williams proved R317 in 1977, Williams and Dubner took R1031 in 1986. Granlund completed a search up to 45,000 in 1998 using two months of CPU time on a parallel computer. It was extended by Dubner in 1999 with the discovery of R49081, and by L. Baxter R86453 in 2000.

Q(4) Does there exist a prime number p such that p does not divide any repunit number Rn? If yes, then show the minimum one.

I think that my question Q(4) is still open. Considering that Williams and Seah [1979] already factored the range of 2<=k<=1000 and told nothing of this, supposedly Q(4) may not hold. However as you see the factoring repunit table R[n] is a very sparse table, it is too early to say that it surely doesn't.

M.N.


p.s. Although I wrote that all of Rn up to n=1000 are factored, according to some sites, there still remain so many unfactored numbers even in the 100 digits order. check http://homepage2.nifty.com/m_kamada/math/11111.htm.

blurulr6.gif (2318 ???)

-------- Original Message No.4 --------
Subject:    RE: [theory-edge] Re: Recurrent Number
Date:     Thu, 3 Mar 2005 22:31:46 +0900
From:     babalabo <babalabo@aya.or.jp>
To:     <theory-edge@yahoogroups.com>

Hi Dick!

I've found my conjecture stating, "|K| is zero for every recurrent number" Q(2.2) was wrong.  I checked the decimal numbers 1/n for n=2 to 50.

record format: [-#+>], [ n], [K:U], [K*n:U*n], [|U|=length of U], [prime/composite]
recursion type: -:non-recurrent, #:recur, with no overlap :999...9, >:recur with null overlap 0:999...90, +:recur with non-null overlap.

n   fixed part:recursion unit U fixed part:U*n |U| p/c
- 2 F 5:0 10:0 0 p
# 3 n :3 :9 1 p
- 4 F 25:0 100:0 0 c
- 5 F 2:0 10:0 0 p
+ 6 U 16:6 96:36 1+1 c
# 7 N :14285 7 :99999 9 6 p
- 8 F 125:0 1000:0 0 c
# 9 n :1 :9 1 c
- 10 F 1:0 10:0 0 c
# 11 N :09 :99 2 p
+ 12 U 083:3 996:36 1+1 c
# 13 N :07692 3 :99999 9 6 p
> 14 R 0:714285 0:9999990 7>6 c
> 15 U 0:6 0:90 1+1 c
- 16 F 0625:0 10000:0 0 c
# 17 N :05882 35294 11764 7 :99999 99999 99999 9 16 p
> 18 U 0:5 0:90 2>1 c
# 19 N :05263 15789 47368 421 :99999 99999 99999 999 18 p
- 20 F 05:0 100:0 0 c
# 21 n :04761 9 :99999 9 6 c
> 22 R 0:45 0:990 3>2 c
# 23 N :04347 82608 69565 21739 13 :99999 99999 99999 99999 99 22 p
+ 24 U 0416:6 9984:144 2+1 c
- 25 F 04:0 100:0 0 c
> 26 R 0:38461 5 0:99999 90 7>6 c
# 27 n :037 :999 3 c
+ 28 R 03571 428:57142 8 99999984:15999 984 2+6 c
# 29 N :03448 27586 20689 65517 24137 931 :99999 99999 99999 99999 99999 999 28 p
> 30 U 0:3 0:90 2>1 c
# 31 N :03225 80645 16129 :99999 99999 99999 15 p
- 32 F 03125:0 100000:0 0 c
# 33 n :03 0:99 2 c
> 34 R 0:29411 76470 58823 5 0:99999 99999 99999 90 17>16 c
> 35 R 0:28571 4 0:99999 90 7>6 c
+ 36 U 027:7 972:252 2+1 c
# 37 N :027 :999 3 p
> 38 R 0:26315 78947 36842 105 0:99999 99999 99999 9990 19>18 c
# 39 n :02564 1 0:99999 9 6 c
- 40 F 025:0 1000:0 0 c
# 41 N :02439 :99999 5 p
> 42 R 0:23809 52380 95 0:99999 99999 990 13>12 c
# 43 N :02325 58139 53488 37209 3 :99999 99999 99999 99999 9 21 p
+ 44 R 0227:27 9988:1188 2+2 c
> 45 U 0:2 0:90 2>1 c
> 46 R 0:21739 13043 47826 08695 65 0:99999 99999 99999 99999 990 23>22 c
# 47 N :02127 65957 44680 85106 38297 87234 04255 31914 89361 7 :9999999....9 46 p
+ 48 U 02083:3 99984:144 2+1 c
# 49 N :02040 81632 65306 12244 89795 91836 73469 38775 51 :9999999...9 42 c
- 50 F 02:0 100:0 0 c

- type: 2,4,5,8,10,16,20,25,32,40,50 (11)
# type: 3,7,9,11,13,17,19,21,23,27,29,31,33,37,39,41,43,47,49 (19)
> type: 14,15,18,22,26,30,34,35,38,42,45,46 (12)
+ type: 6,12,24,28,36,44,48 (7)

'+'Type numbers are those I missed. As you wrote, "the repeater is 000... iff n has form 2a5b". This is the case '-' type. '#'Consists of prime numbers other than 2 nor 5, and their products. '>' and '+' are mixed products of '-' and '#'. We know that every numbers are products of some prime numbers. +Type number is a product of 2 and 5. #Type is without 2 and 5. > and + types contain both (2 or 5) and others. Now we can say,

[1] A multiple m=n*x of a recurrent number n is recurrent too.
[2] A multiple m=x*y of non-recurrent numbers x, y is non-recurrent.
[3] Every non-recurrent number n is to be expressed as 2p5q, and any other numbers are recurrent.
[4] Especially all prime numbers are recurrent, excluding 2 and 5.
[5] Every recurrent number n of type '#' is a divisor of some number m of length k such as 111...1=(10k-1)/9. as well a recurrent number of type '>' divides a number such as 9999...90.
[6] A number n of form 111...1 is of type '#'.
[7] For any recurrent number n, the length k of recursion unit U of n is smaller than n.


Proof of [6]: Apparently n is divisible by neither 2 nor 5. QED.

Proof of [7]: Compute one digit Q[i] of the quotient Q of 1/n step by step. If remainder R=10i-SQ[i] (sorry, not accurate...) appears more than once, then the quotient Q already contains a recursion unit. In other words, the remainder R must be different for each computation until it begins recursion, while R < n implies i < n. QED.

A(1) No. See the proof [7] above.
A(2) Yes. Type '+' is the case. (Type '>' is assumed to be K=00..0.)

Q(3) Prove or disprove: suppose a number n of form 111...1 of length k, if k is prime then n=11.
Q(4) Does there exist a prime number p such that p does not divide any number n of form 111...1. If any, then show the minimum one.

Rem: I was somewhat confused. Question (2) consists of two parts, (2.1) and (2.2). I meant here that Q(2.1) was wrong. While Q(1) had asked if the proposed proposition table was totally true or not, but Q(2) was not in the table and I did not asserted in that way. So A(1) may not be determined yet...

 

blurulr6.gif (2318 ???)

-------- Original Message No.3 --------
Subject:     RE: [theory-edge] Re: Recurrent Number
Date:     Thu, 3 Mar 2005 14:52:16 +0900
From:     babalabo <babalabo@aya.or.jp>
To:     <theory-edge@yahoogroups.com>

Hi Max!

After all, those numbers must be all rationals. Because they are repeated over and over in speeches, writings, books, etc. Don't you think?

It may be if it is that sanity is doing the same thing over and over and expecting the same results. BTW I might have confused/mistaken radical and rational so far. As far as I recall it was said, "radical is rational" by Mao, the founder of the communist party of China.

 

blurulr6.gif (2318 ???)

-------- Original Message No.2 --------
Subject: RE: [theory-edge] Re: Recurrent Number
From: "babalabo" babalabo@aya.or.jp
Date: Thu, 3 Mar 2005 14:32:46 +0900
To: <theory-edge@yahoogroups.com>

Hi Dick!

If the decimal expansion eventually repeats, the number is rational. This is equivalent to the definition of rational. If it never repeats, the number is irrational.

Sorry. I've made my same old mistake once again. ^^;

The non-zero, non-repeating parts "K" are much more the rule than the exception and all numbers that share a particular, eventual repeating pattern have common factors. For example, amongst 1/n, the repeater is 00000... iff n has form 2^a 5^b. Each repeating pattern has an infinity of "K"'s to add in front. Put anything you like in front of the repeating pattern and you have a rational number, just like counting.

You are right. but when I say a (non-)recurrent number n, n is assumed to be an integer implicitly but not a general rational number. I claim that every non-recurrent number(integer) has a form of 2a5b, further I conjectured that |K| is zero for every recurrent number. This is equivalent to your "the repeater is 00000... iff n has form 2a5b." To consider a recurrent/non-recurrent number makes things very simple.

As far as length of the repetition string, I recall seeing something on it on Mathworld awhile back, but the subject heading escapes me at the moment (maybe try rational number). There are proven bounds, if not exact formulas for the "rep length", I am pretty sure.

As far as I've checked on some small samples, it seems that the length doesn't become so much long. Although currently as I have not a multi-precision arithmetic, my experiment is very restricted. What about the length of K, non-repeating part, for non-recurrent number n?

Michiro

 

blurulr6.gif (2318 ???)

-------- Original Message No.1 --------
Subject: [theory-edge] Recurrent Number
Date: Thu, 3 Mar 2005 06:49:24 +0900
From: babalabo <babalabo@aya.or.jp>
To: Theory-Edge <theory-edge@yahoogroups.com>

Hi Vlad and all!

I've dropped into a puzzle while I was helping a schoolgirl's homework. Say that a decimal number n=0.xxxxyyyy... has two parts, non-recurrent part xxxx and recurrent part yyyy.... We know that an irrational number has a non-recurrent part of infinite length, while a radical rational number has a finite (possibly zero) length non-recurrent part. We say a number n is recurrent iff 1/n has an infinite recurrent part; otherwise n is non-recurrent. e.g. 3 is recurrent, but 2 is not. We call a minimal non-recurrent part in a decimal number n the recurrent unit of n. E.g. the recurrent unit of 0.6123123... is '123'. Propositions,

[1] A multiple m=n*x of a recurrent number n is recurrent too.
[2] A multiple m=x*y of non-recurrent numbers x, y is non-recurrent.
[3] Every non-recurrent number n is to be expressed as 2p5q, and any other numbers are recurrent.
[4] Especially all prime numbers are recurrent, excluding 2 and 5.
[5] Every recurrent number n is a divisor of some number m of length k such as 111...1=(10k-1)/9. for example 57=3*19 divides 111...1 (18digits) into 1949317738791423.
[6] Hence it can be said that a number n=111111...1 is to be expressed as a product of prime numbers p1,p2,...pk excluding 2 and 5.

Q(1) Are these correct? number theory may be your field, so I ask you a bit.
Q(2.1) Are there any recurrent numbers n of which recurrent unit are very long, for example longer than n?
Q(2.2) Are there any recurrent numbers n which have non-zero non-recurrent part? i.e., 0.KUUU..., where U is the recurrent recursion unit and K is not totally of '0' sequence.

Michiro

p.s.: Consider the inverse of a recurrent number n=7, 1/7=0.142857142857... Thus its recurrent unit U=142857. now multiply U by n, and then we get U*7=142857*7=999999=9*111111. Here is a table of 111...1s up to k=10.

11=11
111=3*37
1111=11*101
11111=41*271
111111=3*7*11*13*37
1111111=239*4649
11111111=11*73*101*137
111111111=3*3*37*333667
1111111111=11*41*271*9091

You would notice that if digit k of m=111...1 is prime, then m is a product of *two* prime numbers. Because if k is not a prime, then we can partition m into like '111','111','111',..., and '111' recurs by itself, while a prime length m has no such a recursion. I guess that to find a recurrent unit isn't any hard. any usage of the table? Where does the theory go if we do use other decimal systems than 10?

Q(3) Are there any integers k such that M(k)=(10^k-1)/9 is a prime other than M(2)=11.

blurulr6.gif (2318 ???)

Definitions, Propositions and Questions

< Definitions >

(1) base b A real number x can be represented using any integer number b as a base (alternatively radix or scale). The choice of a base yields to a representation of numbers known as a number system. In base b, the digits 0, 1, ..., b-1 are used (where, by convention, for bases larger than 10, the symbols A, B, C, ...are generally used.
(2) integer division \ Integer division is a division denoted \ in which the fractional part (remainder) is discarded. Integer division can be defined as a\b=floor(a/b). To represent the remainder part, we apply the notation a\b=q...r, where q is the quotient of A\B and r is the remainder.
(3) recurrent number n A rational number n is said to be recurrent on b-base iff the b-base decimal representation of 1/n is of infinite length 
(4) recursion unit U
U(b,n)
The number expressed with a portion of the minimum recurrent digits of a decimal representation of the inverse 1/n of a number n on b-base decimal system. Sometimes the number/length u of the digits may be referred as u-length and denoted as |U|=u. For example in 10-base, for n=3, 1/3=0.3333... u=1 and U=3, and for n=7, 1/7=0.1428571428..., u=6 and U=142857, for n=24, 1/24=0.041666..., u=1, U=6. See definition (15).
(5) non-recurrent part K Fixed digits of a decimal representation D of b-base number system of the inverse 1/n of a rational number n. D is seen to be 0.KUUU... For convenience if |K|>0 we sometimes regard K+U as the non-recurrent part of the number.
(6) recursion unit length k The number k of digits of the recursion unit U of a recurrent number n. If k is 0, then n is non-recurrent. For convenience we use k=|U| notation.
(7) repunit number Rk
Rb(u)
R(b,u)
A repunit number Rk is a number consists of k>0 copies of digit 1. In base 10, Kr=(10k-1)/9. Generally repunit on b-base is a number of the form S[i=0 to u-1]bi = (bu-1) / (b-1). R(b,u) denotes a repunit number Ru on b-base. Alternatively RBI(u) is used too.
(8) recursion type #
>
+
-
type |K| |U| n*U factors of n n numbers
# 0 k Rk*(b-1) A={prime to b} 3,7, 9,11,13,17,19,21,
23,27,29
non-radical
> 0 k Rk*b*(b-1) C={mixed AxB} 14,18,22,26,30 radical
+ m k ??? C={mixed AxB} 6,12,15,24,28 radical
- m 0 0 B={factors of b} 2,4,5,8,10,16,20,25 fundamental
(9) GCM (GCD,GCF) (a,b) gcd(a,b) Greatest common measure (alternatively divisor, denominator, factor) for natural numbers, a and b. If (a,b)=1, then a and be are mutually (relatively) prime. Sometimes would be expressed as gcd(a,b).
(10) pseudoprime   A composite which satisfies all the conditions of Fermat's little theorem.
(11) originator   A recurrent number n such as nU=Rk, where U is the recursion unit of n and k=|U|. An originator generates a repunit number Rk, while Rk possibly has multiple originators.
(12) totient function f(n) The totient function f(n),also called Euler's totient function, is defined as the number of integers <=n that are mutually prime to n, where 1 is counted as being mutually prime to all numbers. For example, there are eight totatives of 24 (1, 5, 7, 11, 13, 17, 19, and 23), so f(24)=8.
(13) radical, non-radical, ultra-radical, fundamental numbers    A number n on a b-base system is radical (with the radix b) iff some factor of n is a factor of either b or b-1; otherwise n is non-radical. As well an ultra-radical number is a number such that all of its factors are a factor of either b or b-1, while a fundamental number is a number such that all of its factors are a factor of the base b. For example in 10-base, n=7, 11, 13, 17, 19, 23,.., 49, 77,... are non-radical numbers, and n=2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16,... are ultra-radical numbers, while n=14, 21, 22, 26, 33, 34, 39... are radical but not ultra-radical numbers. No prime p is non-radical simultaneously on the bases both b and bp-1.
(14) u-length k
u
The length u=n of a repunit number Rn=(bn-1)/(b-1)=S[i=0 to n-1]bi. The term "u-length" is also applied to the length of a recursion unit U(b,n) as (15), i.e., the period of recurring decimal on b-base of the reciprocal of a number n.
(15) u-length function y(b,n) Given mutually prime numbers n and b, there exist nonnegative integer x<n and positive integers y and z such that z=x*by \n...x, that reads n divides x*by, the quotient z, and the remainder x, in other words, n*z+x=x*by. A set of {x,y,z} exists infinitely. u-length function y(b,n) is defined as the minimum such number y, as well recursion unit U(b,n) as the minimum such number z. Accordingly n*U(b,n) = r*(by(b,n)-1), where r is the first dividend that appears as the remainder.
(16) multiplicative order,  haupt-exponent,  modulo order e
ordna
On(a)
Given numbers b and n, the smallest exponent e>=1 for which be=1 mod n, is called the multiplicative order (or haupt-exponent or "modulo order") of b (mod n). Multiplicative orders exist for n that are mutually prime to b, i.e., gcd(b,n)=1. For example, the multiplicative order of 10 mod 7 is 6, as 106=1 mod 7. ordnb gives the length of the recursion unit of the reciprocal of n on b-base. By Lagrange's theorem, ordnb always divides f(n). For non-radical numbers n on b-base decimal system, ordnb=y(b,n).
(17) primitive root g If ordn g is actually equal to f(n) and therefore as large as possible, then g is called a primitive root modulo n. This means that the group U(n) is cyclic and the residue class of g generates it. Not every number n has a primitive root, but prime numbers always do.
(18) generalized multiplicative order, discrete logarithm m If a is an arbitrary integer relatively prime to n, then there exists among the numbers 0,1,2,...f(n)-1 exactly one number such that a=gm mod n. The number m is then called the generalized multiplicative order (or discrete logarithm [Schneier,1996], or index [Nagell 1951]).

< Propositions > C:Conjecture by MN, D:Proposal by DGD, T:Theorem

[1] C A multiple m=n*x of a recurrent number n is recurrent too.
[2] C A multiple m=x*y of non-recurrent numbers x, y is non-recurrent.
[3] C Every non-recurrent number n is to be expressed as 2p5q, and any other numbers are recurrent.
[4] C Especially all prime numbers are recurrent, excluding 2 and 5.
[5] C Every recurrent number n is a divisor of some number m of length k such as 111...1=(10k-1)/9. For example, 57=3*19 divides 111...1 (18digits) into 1949317738791423.
[5'] C Every recurrent number n of type '#' is a divisor of some number m of length k such as 111...1=(10k-1)/9. As well a recurrent number of type '>' divides a number such as 9999...90.
[6] T A number n of form 111...1 is of type '#'.
[7] T For any recurrent number n, the length k of recursion unit U of n is smaller than n.
[8] T A repunit number Rn can be prime only if n is prime.
[8'] T Let p be a prime number which is neither 2 nor 5, and the recursion unit of p be U, then pU/9 is a repunit number Rn, i.e., pU=10n-1.
[9] T Let m be an integer without factor 2 nor 5, and the recursion unit of m be U, then mU/9 is a repunit number Rn, i.e., mU=10n-1.
[9'] T In b-base decimal system, for all non-radical numbers n, there exists a repunit number R(b,f(n)) originated from the number n, where f is the Euler totient function. This is equivalent to [14].
[9"] P2
T
Schoolgirl's Homework Conjecture: Let y(b,n) be the minimum number of recurrent digits in b-base decimal expression of the inverse 1/n of a number n. Then for all natural numbers n>1 mutually prime to b and b-1, by(b,n)-1 is divisible by n, as well the repunit number R(b,y(b,n)) is a multiple of n.
[10] T A prime number p > 5 is a factor of at least two repunit numbers such as R*=(10n-1)/9, where n is the smallest number that satisfies 10n-1=0 mod p, and n divides p-1. Anothe one is R+ =(10p-1-1)/9. 
[10'] T For any b-base system, a non-radical prime number p divides at least two   repunits. One is R*=R(b,d)=(bd-1)/(b-1), where d divides p-1 and is the smallest number satisfying bd-1=0 mod p. And another one is  R+=R(b,p-1)=(bp-1-1)/(b-1).
[11] D1
T
In every polynomial field, xk-1 is a multiple of x-1. Moreover if k is composite, say of the form p*q*r..., then xk-1 is a multiple af all xp-1, xq-1,xr-1,...
[12] D2
T
For each primes p,q,r,... > 5, there are infinite repunits multiple of p,q,r, ... and each combination of them (p*q, p*r, p*q*r, ...).
[13] D3
T
Daniele's Formula: For a prime number p, the repunit (10((p-1)*pk^k)-1)/9 is multiple of p(k+1). This implicitly implies [9]. 
[14] D4
T
Given a number b and a number n relatively prime to b, then for all k bk*f(n)-1 is a multiple of n where f(k) is the Euler totient function.
[15] T For any b-base decimal system and natural numbers m and n, if n
is divisible by m, then R(b,n) is divisible by R(b,m). Let q=n/m, then there exist two possible expressions of R(b,n) like R(b,n) = R(b,m)*R(bm,q) = R(bq,m)*R(b,q). Essentially equivalent to [11].
[16] T For any b-base decimal system and natural numbers m and n, if n is a square of m, i.e., n=m2 then R(b,n) is divided by R(b,m), like R(b,n) = R(b,m) * R(bm,m). That is, a repunit R(b,m2) is a product of two repunits R(b,m) and R(bm,m) of the same u-length m. Corollary of [15].
[17] T For a non-radical prime p on b-base, repunit number R(b,(p-1)*p) is divisible by p2. A repunit R(b,(p-1)*p) is factored by two repunits of u-length p and p-1 respectively in two ways like R(b,(p-1)*p) = R(b,p-1) * R(bp-1,p) = R(b,p) * R(bp,p-1). Each of these repunits are multiple of p. This result is extendable to [13].
[18] P1
T
For any natural number n>2 on b-base decimal system, the value of u-length function y(b,n)>0 always divides the value of Euler's totient function f(n), i.e., gcd(f(n),y(b,n)) = y(b,n). If n is a prime, then y(b,n) divides n-1.
[19] C For any b-base decimal system, for any number n with y(b,n)>0, the quotient f(n)/y(b,n) is an ultra-radical number on the base b, where f(n) is the Euler's totient function and y(b,n) is the u-length function of n.
[20] T Multiplicative orders exist for n that are not factors of b, i.e., there exists the smallest exponent e>=1 such that be=1 mod n. This implies [9"]. By Fermat's little theorem, if n is prime, then e=n-1 satisfies the congruence, and by Euler's totient theorem e=f(n) also satisfies the congruence generally. Our claim [9"] is that e=y(b,n) not only satisfies the congruence, but also it is the smallest, i.e., the multiplicative order of b mod n.
[21] P3
C
A repunit R(b,k) is factored into distinct repunits and primes.
[22] P4
T
A repunit number R(b,k) originates itself on any b-base.
[23] P5
C
If the u-length y(b,n)=n-1 for a number n, then n is prime. Equivalent to [26].
[24] P6
C
If y(b,n) is a prime, then f(f(n))=0 mod y(b,n)-1 else R(b,y(b,n)) has repunit factors. This proposition is true even if n is radical.
[25] P7
C
(1) If n is fundamental, then y(b,n)=0.     
(2) If n has just one non-radical prime factor, then y(b,n) is prime.     
(3) If n has more than one prime factors, then y(b,n) is composite.
[26] C Prime Criterion:
A natural number n is prime iff there exists some base b such that y(b,n) = n-1. Equivalent to P4 [23]. Fermat's theorem implies the only if part of the statement.
[27] C Composite Criterion:
If n is an odd composite, then there exists some base b such that factors of the psi number y(b,n) forms a factor of n like the following manner. Suppose y and n have factors like y(b,n)=f1*f2*...*, and n=p1*p2*...*. Then there exists some combination of factors taken from {f1, f2, ...} such that pi = fi1*fi2*...fik + 1.
Fermat's Little Theorem
If p is a prime number and b a natural number, then (1) bp=b mod p. Furthermore, if p does not divide b, then there exists some smallest exponent d such that (2) bd-1=0 mod p, and d divides p-1. Hence (3) bp-1-1=0 mod p.
Euler's Totient Theorem
A generalization of Fermat's little theorem. Let f(n) denote the totient function. Then bf(n)=1 mod n for all b mutually prime to n.
Lagrange's Group Theorem
If G is a finite group and H is a subgroup of G, then the order (that is, the number of elements) of H divides the order of G. This implies Fermat's little theorem, Euler's Totient theorem, and [18].

< Questions >

(1) Are these propositions correct? ?
(2.1) Are there any recurrent numbers n of which recurrent unit are very long, for example longer than n? no
(2.2) Are there any recurrent numbers n which have non-zero non-recurrent part? i.e., 0.KUUU..., where U is the  recursion unit and K is not totally of '0' sequence. yes
(3) Prove or disprove: Suppose a number n of form 111...1 of length k, if k is prime then n=11. false
(3') Repunit number Rn is prime only if n=2 and Rn=11. Right? no
(4) Does there exist a prime number p such that p does not divide any number n of form 111...1. If any, then show the minimum one. no
(4') Does there exist a prime number p such that p does not divide any repunit number Rn? If yes, then show the minimum one. no
(4") Prove or disprove the proposition [8]. true
(5) If for all prime p there are repunits multiple of all powers of p, or not. (DGD) ?
(6)    
Lehmer's Totient Problem
If there exist any composite numbers n such that f(n)|n-1, where f(n) is Euler's totient function. If such a number exists, then it must be a Carmichael number because y(b,n)|f(n)|n-1, and then bn-1=1 mod n. No such number is known so far.

blurulr6.gif (2318 ???)