Re: Prime Factorization and Digit Congruence

From: Daniel W. Johnson (panoptes_at_iquest.net)
Date: 07/19/04 

Date: Mon, 19 Jul 2004 00:57:21 -0500

Ross A. Finlayson <raf@tiki-lounge.com> wrote:

> For the phi function, I think you mean the totient function, Euler's
> phi. phi(x) for positive integer x is the count of integers less than
> x that are relatively prime to x, sharing no factors, plus one for
> one.

Yes. (But what's this "plus one for one"?)

> So phi(7) is 6, for 1, 2, 3, 4, 5, and 6, for prime p phi(p)=p-1.
>
> http://mathworld.wolfram.com/TotientFunction.html
> http://www.research.att.com/projects/OEIS?Anum=A000010
>
> This is interesting, a theorem of Euler states that if integers a and
> n have no common non-unit factors, that gcd(a, n)=1, that they're
> relatively prime, that they're coprime, that a^phi(n) mod n = 1.

Ah, I forgot that that had been proven directly.

> http://primes.utm.edu/glossary/page.php?sort=EulersTheorem
>
> You mention in decimal about phi(98) being 60, 10^60 mod 98 = 1.

Typo: phi(99) = 60, so 10^60 mod 99 = 1.

> Trivially, a^0 mod 0 = 1. In determining a form for a divisibility
> test for 99 in base ten, it may well be completely easier to go to
> base 100 where each digit is added and that result is tested for
> divisibility by 99, reducing to the case of b and b-1, instead of
> groups of 60, with determining what pairs x-n, n, are the "residues"
> in each integral modulus. For example in the case of 7, a prime
> number, there are three pairs phi(7)/2 = 6/2=3, and they are uniquely
> 7-1 and 1, 7-2 and 2, and 7-3 and 3.
>
> In looking for the cycle length, if it's to be phi(x) then a^ 2phi(x)
> mod x must equal 1. I wonder what is 10^120 mod 99. If it's 1, and so
> on and so forth a ^ n(phi(x), and also for each c from 0 to phi(x)-1
> that a ^ c mod x = a ^ n(phi(x))+c mod x, then it is similar to 7 and
> the cycle length of phi(7)=6. It may be that each residue in the
> cycle is unique, or not, I don't know, and if the cycle length is less
> than x-1 then some residues, remainders, do not exist as any of b^c
> mod x, where c is the cycle length.

I don't know where that "2" came from. By the Euler theorem you
mentioned, a^phi(x) mod x must equal 1. But 10^120 = (10^phi(99))^2
must be congruent to 1^2 (mod 99).

> So I'm wondering about the cycle repetition for a cycle of phi(x), why
> that is so, and what remainders there of the possible values for c
> from 0 to x-1 for each of b^0=1 to b^(phi(x)-1), and also about from
> b^0 to b^c.

Consider the calculation of 1/x in base a by long division. The
remainder after k digits is simply the remainder when a^k is divided by
x. Since a^phi(x) has a remainder of 1, that means you will have a
definite feeling of déjà vu after phi(x) digits.

> The abovementioned resources don't directly describe a method of
> determining phi(n) without counting the totatives of n, there may well
> be a recurrence relation or family to determine that value, yet its
> very presence in the integer sequence dictionary as its own definition
> leads one to think that it is not obvious or known.

phi(n) can be calculated by multiplying n by (p-1)/p for each of the
distinct prime factors p of n. For example, phi(99) = 99 * (2/3) *
(10/11) = 60.

> So it looks like we can talk about Euler's totient function, phi, and
> Euler's totient theorem, for coprime a and n a^phi(n) mod n = 1.
>
> It's nice to remember the law of small numbers, while that is so,
> there is much to be taken from decimal seven. The "cycle length" is
> x-1, but more importantly it's phi(x). Each of the values mod 7,
> except for zero, occur for b^c, because seven is coprime to ten, and
> prime.

Note that the minimal cycle length could be less than phi(x); there is
nothing about the long division I mentioned to prevent seeing a
remainder of 1 before phi(x) digits have been calculated. For example,
dividing by 11 in base 10 will repeat after 2 digits, not 10. And in
any base, dividing by 99 will repeat at the 30th digit at the latest.
But the minimal cycle length must always be a factor of phi(x). (If a^6
and a^15 are both congruent to 1 in a certain modulus, it is easy to
calculate that the same must be true of a^3.)

> I guess I wonder how to determine the minimum cycle length, and as
> well, a closed form for phi. These are integers, prime and composite,
> abundant, deficient, and perfect, squares, cubes, and other powers,
> and so on and so forth.

A closed form for phi (given the prime factorization) was stated above.
The minimum cycle length is another matter; there are primes for which
the minimum cycle length will be one less than the prime. The 6 digit
loop for 7 is not unusual. And even using a "-1" to cut the effective
cycle in half (like the 3-digit groups for 7) is not going to do much
for efficiency. 

-- 
Daniel W. Johnson
panoptes@iquest.net
http://members.iquest.net/~panoptes/
039 53 36 N / 086 11 55 W

Relevant Pages