Don Reble, Jun 06 2016

We will show that the following five definitions are equiva;ent:

(D1) Positive numbers divisible by 8 or by the square of an odd prime. 

(D2) Moduli n for which there exist affine maps f:x->a*x + b modulo n, with a>1, such that f has order n in the affine group. 

(D3) Numbers n such that A005361(n) < A003557(n).

(D4) Numbers i such that there is a smaller positive number j such that (i+j)/2 and sqrt(i*j) are integers. 

(D5) Numbers n such that A008475(n) is different from A001414(n). 

Proofs:

   Let S1,...,S5 be the integer sets defined by D1,...,D5.

   Definitions:
   - component of n: for any prime p, the highest power of p which divides n.
   - big component of n: any composite component, except 4

   The point of a big component p^k is that p^k > p*k, while for other
   components, p^1 = p*1, and 2^2 = 2*2. Also, D1 can be written
   "Positive numbers with a big component."


   --- S1 = S5 ---

   A008475 maps n = product(p^k) to a(n) = sum(p^k).
   A001414 sums the prime factors of n (including repetitions);
           a(n) = sum(p*k).

   If sum(p^k) isn't sum(p*k), then for some component, p^k isn't p*k,
   so p^k is a big component.

       So S5 is a subset of S1.

   If n has a big component, that component makes A008475 bigger than
   A001414.

       So S1 is a subset of S5.

 --- S1 = S2 ---

   Using Knuth's Theorem A, [TAOCP volume 2, second edition,
   section 3.2.1.2, p. 16], we see that there is such an affine map
   f:x->a*x + b modulo n iff
       - each prime dividing n also divides a-1, and
       - if 4 divides n, then 4 also divides a-1.
       (Also, b must be coprime to n; b=1 suffices.)
   We may take a to be within [2,n-1].
   (a=1 works, but it's forbidden, since we have "with a>1")
   If n is square-free, then n divides a-1: all a-values in [2,n-1]
   fail, and there is no such map.
   So n is not square-free. If the only composite component of n is 4,
   then again n divides a-1.
   Therefore n is divisible by 8 or by the square of an odd prime.

       So S2 is a subset of S1.

   If n is divisible by 8, let d be the highest odd factor of n,
   let a=4d+1. 1 < a=4d+1 < 8d <= n.
   If n is divisible by odd p^2, let a=(n/p)+1.
   1 <= n/(p^2) < a=(n/p)+1 < n.
   Either way, Knuth's theorem shows that there is a suitable affine
   map using that a-value.

       So S1 is a subset of S2.


   --- S1 = S3 ---

   A005361 gives the product of the exponents in n = product(p^k).
   A003557 gives n divided by its largest square-free divisor.

   If n is square-free, than A003557(n) = 1 = A005361(n).
   If n is 4 times an odd square-free number, then
   A003557(n) = 2 = A005361(n).
   So if A003557(n) > A005361(n), n must be divisible by 8 or by the
   square of an odd prime.

       So S3 is a subset of S1.

   First, show that A005361(n) <= A003557(n) always.
   Let n = product(p^k); then A005361(n) = product(k),
   A003557(n) = product(p^(k-1)).
   If p^k is a big component, then p^k > p*k, and p^(k-1) > k.
   If p^k is not big, then p^k = p*k, and p^(k-1) = k.
   Each factor of A003557 is >= the corresponding factor of A005361,
   so the product is >=.

   Let n be a element of S1; let c=p^k be a big component of n.
   Then p*A005361(n) = p*k*A005361(n/c) <= p*k*A003557(n/c)
       < (p^k)*A003557(n/c) = p*(c/p)*A003557(n/c) = p*A003557(n).
   Therefore A005361(n) < A003557(n) and n is in S3.

       So S1 is a subset of S3.


   --- S1 = S4 ---

   If i is divisible by 8, then let j=i/4; if i is divisible by an odd p^2,
   let j=i/(p^2). Then 0<j<i, and (i+j)/2 and sqrt(ij) are integers.

       So S1 is a subset of S4.

   Let i, an element of S4, equal (a^2)*b, where b is square-free.
   If (i*j) is a square, then j=b*(c^2), for some value of c. D4 says
   0<j<i; therefore 0<c<a and 1<a.
   If a=2, then c=1, and (i+j)/2 = 5b/2: that is an integer,
   so b is even, and 8 divides i.
   If a is a higher power of two, then 8 divides i.
   Otherwise a is divisible by an odd prime p, and p^2 divides i.

       So S4 is a subset of S1.