|
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
|
| Let phi be Euler's function, i.e. for each natural n > 0, the number of
naturals relatively prime to n. Then for each natural n and each
natural a relatively prime to n, we have:
phi(n)
a = 1 mod n.
This is a corollary of Lagrange's theorem which states that for each
finite group of order m and each element a of the group:
m
a = 1.
Apply to the multiplicative group of Z/nZ, the ring of integers modulo
n, whose order is m = phi(n).
Now, if we take a = 10 and n relatively prime to 10, we get:
phi(n) phi(n)
10 = 1 mod n. That is, n divides 10 - 1.
Let m = phi(n). That means that:
1000 ... 000 = 1 mod n (m 0's) or
999 .... 999 = 0 mod n (m 9's)
If in addition, n is relatively prime with 3, we can divide by 9 and we get:
111 ... 111 = 0 mod n .
The smallest number is given by:
111 ... 111 = 0 mod n, with r 1's, where r is the order of 10 in the
multiplicative group of Z/nZ. Hence, r is a divisor of m = phi(n).
For example, 10 is of order 3 in (Z/37Z)*, the multiplicative group of
integers mod 37. So: 37 divides 111. 111 = 3 x 37.
If n is divisible by 3, well, I don't know the answer right now.
That was one of the questions I was asked when I graduated as a math
teacher, some 17 years ago...
Herv�
|
| 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.
|