« A fortunately timed trip
Factorization of Beethoven numbers »
h1

Constructing Niven repunit – proofs

July 23, 2009

 

Revisiting the Saturday problem.

Given a number made only out of 1s, when is it exactly divisible by the number of 1s. How do we construct Niven Repunits?

This isn’t a tough problem, but my maths is rusty and I struggled to find a proof. I also wanted a proof that anyone with high school maths could follow.

In previous posts I put down some conjectures – it’s time to show some proofs. I’ve tried to make these as simple as possible.

Definitions

R_{n}^{b}

is a repunit (made of repeated 1s with n digits in number base b).

Algebraically they can be written as

R_{n}^{b}=\sum_{i=0}^{n-1}b^i=\frac{b^n-1}{b-1}

A Niven repunit is divisible by the sum of its digits.  As all the digits are “1” this is equivalent to saying it’s divisible by the number of digits.

ie. A Niven repunit satisfies:

 

R_{n}^{b}\equiv0\pmod{n}

 

A pretty obvious lemma

First we’re going to show if:

a\equiv1\pmod{p}

then:

a^n\equiv1\pmod{p}
Proof (although you probably don’t need it)

When

n=0

 

a^0=1

 

a^0\equiv1\pmod{p}

Using induction

Assume

a^i\equiv1\pmod{p}

 

a^{i+1}=a^ia

 

\equiv1a\pmod{p}

We know:

a\equiv1\pmod{p}

So

1a\equiv1\pmod{p}

 

Easy Niven repunits theorem

This first theorem lets us find our first Niven repunits really easily by just ensuring the number of digits is a factor of one less than the number base.

Theorem

Given a repunit with n digits in base b.

When n is a factor of b-1

The repunit will be exactly divisible by n

IE.

R_n^b\equiv0\pmod{n}

If n is chosen such that

b-1\equiv0\pmod{n}

Proof

Because:

b-1\equiv0\pmod{n}

We know:

b\equiv1\pmod{n}

One definition of a repunit is:

R_n^b=\sum_{i=0}^{n-1}b^i

So using

b\equiv1\pmod{n}

and the lemma we arrive at.

R_n^b\equiv\sum_{i=0}^{n-1}b^i\equiv\sum_{i=0}^{n-1}1\equiv{n}\equiv{0}\pmod{n}

 

Second set of Niven repunits

This second theorem allows us to create huge Niven repunits based on the first and second type of repunit. e.g. Why repunits with 2,997 are Niven.

Theorem

Given a Niven repunit, a new Niven repunit can created with a number of digits that is obtained by multiplying the number of a digits in the first repunit by any factor of the first repunit.

R_n^b\equiv0\pmod{n}

Choosing a value of p such that:

R_n^b\equiv0\pmod{p}

Then:

R_{np}^b\equiv0\pmod{np}

Proof

By definition of a repunit:

R_{np}^b=\frac{b^{np}-1}{b-1}

Multiplying top and bottom by

b^n-1

 

=\frac{b^n-1}{b^n-1}\frac{b^{np}-1}{b-1}

Rearranging

=\frac{b^n-1}{b-1}\frac{b^{np}-1}{b^n-1}

Moving the powers about

=\frac{b^n-1}{b-1}\frac{{(b^n)}^p-1}{b^n-1}

 

Note that by the definition of repunit:

R_n^b=\frac{b^n-1}{b-1}

and

R_p^{b^n}=\frac{{(b^n)}^p-1}{b^n-1}

So

R_{np}^b=R_{n}^bR_{p}^{b^n}

We know our original repunit was divisible by n (because it was a Niven repunit).

ie.

R_n^b\equiv0\pmod{n}

If we can just prove that the other repunit is divisible by p we’ll be done.

It’s not enough to say the first repunit is divisible by p because p and n could be the same number – so just because the 111 is divisible 3 it doesn’t make 111 divisible by 9 – we need to prove the second p digit repunit in base b^n is also divisible by 3 (in that example).

i.e. if:

R_{p}^{b^n}\equiv0\pmod{p}

then

R_{np}^b\equiv0\pmod{np}

We can use a similar proof to the first theorem:

We know:

R_n^b=\frac{b^n-1}{b-1}

and we chose p to be a factor of this so

\frac{b^n-1}{b-1}\equiv0\pmod{p}

So:

b^n-1\equiv0\pmod{p}

So

b^n\equiv1\pmod{p}

any by definition

R_p^{b^n}=\sum_{i=0}^{p-1}(b^n)^i

Remembering

b^n\equiv1\pmod{p}

R_p^{b^n}\equiv\sum_{i=0}^{p-1}(b^n)^i\equiv\sum_{i=0}^{p-1}(1)^i\equiv{p}\equiv{0}\pmod{p}

 

Which is what we wanted to prove.

So in a nutshell

R_{np}^b\equiv0\pmod{np}

Because

R_{np}^b=R_{n}^bR_{p}^{b^n}

 

R_n^b\equiv0\pmod{n}

and

R_{p}^{b^n}\equiv0\pmod{p}

 

Notes

Given these two theorems we can construct huge Niven repunits in any number base. It does seem a bit odd that if we start with a three digit repunit in base 10 we could end up multiplying it by a 37 digit repunit in base 1000!

But if you think about how base 1000 would be represent in decimal and how long multiplication works you’d see that it was:

111×1001001001001…1001

 

If you did the long multiplication you can see why you’d get another repunit and why it would be Niven.

Posted in Uncategorized |

Leave a Comment