|
So, for example, 7 being prime to 10 means some number of 1's, at most 7
of them, is a multiple of 7.
1 nope
11 nope
111 um... nope
1111 ... nope
11111 ... nope
111111 ... yes ! 7*15873
I wonder which n require us to "go all the way". 7 didn't. In other words,
we stopped at 6 7's and didn't have to try 7 7's.
3 goes all the way, since we have to go to 111.
How about 9. It seems to require all 9 1's.
/Eric
|
| My proof of .0: for 1 <= k <= n , we have
1...1 = q(k) * n + r(k) with 0 <= r(k) < n
k digits
Either one of the r(k) is 0 , or apply the box principle to the n - 1
remaining possible values of the r(k) and consider that n is relatively
prime to 10 .
This proof also suggests the following generalization of .0: .0 does not
depend on the numerical base. More precisely:
Let n be relatively prime to r . Then there exists a multiple
of n whose writing in base r has at most n digits, all = 1 .
The result
phi(n)
a = 1 mod n for a and n relatively prime
is known as the Euler or the Fermat-Euler Theorem. There are several
classical proofs for it; the first proof was given by Euler.
Eric's question (.1):
> I wonder which n require us to "go all the way".
As Eric puts it, to "go all the way" means that the smallest k ,
1 <= k <= n , for which n | 1...1 is k = n .
k digits
Herve has proved (.4) that if n is relatively prime to 30 , then
n | 1...1 . As 1 <= phi(n) < n , this means that "we don't go
phi(n) digits
all the way" for n if n is relatively prime to 3 (or, equivalently,
to 9 ).
Transposing Herve's solution to the case of the base r : "we don't go all
the way" in base r for numbers relatively prime to (r - 1) * r .
Now, in base r , we do " go all the way" for n = r - 1 (rule of nines
in base r ). What about the other n not relatively prime to r - 1 ?
Let p(i) , 1 <= i <= s , be the divisors of r - 1 . Take n relatively
prime to r , but not relatively prime to r - 1 ; then
s alpha(i)
n = m * t , where t = PI p(i) ,
i = 1
m is relatively prime to r - 1 and alpha(i) <> 0 for at least
an i (1 <= i <= s).
We have m | 1...1 and t | 1...1 , where 1 <= x <= t .
phi(m) digits x digits
Consider the number u = 1...1 . Then m | u and t | u ,
x * phi(m) digits
hence n | u , but x * phi(m) < x * m = n, so "we don't go all the way"
in base r for n if n has a divisor relatively prime to r - 1 .
What about the n whose only divisors are those of r - 1 ?
Mihai.
|