Re: Prime Factorization and Digit Congruence

From: Ross A. Finlayson (raf_at_tiki-lounge.com)
Date: 07/19/04 

Date: 19 Jul 2004 10:23:00 -0700

panoptes@iquest.net (Daniel W. Johnson) wrote in message news:<1gh5b5k.urn0ti1fyz6awN%panoptes@iquest.net>...
> 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.

Hi Daniel,

One is normally considered not a prime. Also I guess the definition
of relatively prime is sharing no (integer) factors other than one.
phi(99)=60, and there are various methods to compute it that have to
do with the prime factorization or using the divisor function that
returns the number of divisors of a number.

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

About b ^ 2c mod 1, what I'm trying to understand is the direct
reasoning why the cycles repeat, regardless of the remainder of 1
existing for cycle of length phi(x), that the cycle repeats. Your
analogy of dividing one by a number coprime to ten for decimal and
observing the repeating pattern in the decimal representation helps to
see why that would be true.

There are a variety of "closed" forms for determining phi(x), some are
detailed right there in the EIS (Encyclopedia of Integer Sequences)
listing, but they're not rational functions (ratios of polynomials),
nor is there a generating function of sorts that doesn't use the
divisor or other function that at some level depends on sieving the
primes from the integers to get the primes, and recursively
determining these characteristics and others about primes and prime
distributions for each.

In browsing MathWorld, a CRC/Wolfram Science product edited by the
glorious and magnanimous Eric Weisstein, there's an entry for a
"veryprime", a reference for it is given as one of Jim Ferry's posts
to sci.math in 1999. The CRC refers to sci.math! If you find an
error in that, one of a variety of mathematical references published
by the old Chemical Rubber Company, he'll correct it. In the
"Factorial/Exponential Identity, Infinity" thread, I found typos or
brainos, or perhaps a simple mistake, in another CRC publication and a
treatise by Knuth.

About the minimum cycle length, it appears that for any (positive)
integer x that for base b that there are bases b^c where b^c mod x =
b^2c mod x = b^nc mod x, that in a base of some power of b, eg b^c,
b^2c, etcetera that the remainder is a constant, for example b^phi(x).
 Where c can be a factor of phi(x), for example a factor of
phi(99)=60, or one of 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, or 30: 60 is
an abundant number.

About efficiency, I think there is actually much to be gained in terms
of a digit summation congruence technique. You and I, people, can
compute. If given only pencils, much paper, and a hundred digit
decimal number to factorize, we'd be well off to check for these small
factors using these methods, before filling pages with long division,
or calculating the products of large matrices, or using other known
techniques for factorizing large numbers. We could remove the
multiples of ten at one shot. We could each start at once, adding
each element to recursively add the digits of that to check for
divisibility by nine or three, and adding and subtracting in various
group sizes that we calculate provably determine the huge number to be
a multiple of some small factor, and using other divisibility tests.
They're efficient divisibility tests. That would be more efficient.
While the digital computer operates on somewhat different principles
than a human, the fact that it is a worthwhile algorithm to consider
for us, provably in the language of complexity theory of which I am
largely ignorant, lends to that it would be an efficient method for
the computer to use, at least while the cycle fits within a computer
word.

I wonder about which bases would be particularly tractable to these
kinds of methods. For example, in base twelve, the cycles might be
shorter than in base ten, because twelve has more factors than ten.
In a prime base, the cycles would be no less than phi(x), x is coprime
to b. Perhaps we can compare the factors of b and phi(x) to compute
the minimum cycle length given those values.

For that, a lot of time again the computer is a productivity aid for
us. What I hav ein mind with that is to generate charts and lists for
various values of b, x, c, n, b mod x, n^c mod x, phi(x), divisors(x),
the factorizations of b, x, phi(x), etcetera. Then, with charts of
those precomputed values, it might be easier and at least more
leisurely to search further for these connections.

Regards,

Ross F.

Relevant Pages

  • Re: Prime Factorization and Digit Congruence
    ... > the cycle length of phi=6. ... remainder after k digits is simply the remainder when a^k is divided by ... dividing by 99 will repeat at the 30th digit at the latest. ... a closed form for phi. ...
    (sci.math)
  • Re: Factoring integers on a classical computer
    ... I realized my mistake when I saw Tim's post and addressed a ... and phi is a multiplicative function. ... I don't think I was lucky in finding a cycle out of my calculations. ...
    (sci.math)
  • Re: Factoring integers on a classical computer
    ... I realized my mistake when I saw Tim's post and addressed a ... and phi is a multiplicative function. ... I don't think I was lucky in finding a cycle out of my calculations. ...
    (comp.theory)
  • Re: Power of 2 with all even digits?
    ... An alternative statement of the problem is whether any powers of two ... above 1024 have only digits less than 5 is their base 10 representation. ... the smallest value in the cycle is twice as big. ... If all values in the cycle contain odd digits then once you've reached ...
    (sci.math)
  • Re: Software advice
    ... as they did less per cycle. ... It's an IBM Electric Typewriter Model E. moving carriage...type bars.... ... Each addressable core loc had 6 ... Addresses were 5 digits. ...
    (rec.arts.sf.fandom)