A Note on a Theorem of Rotkiewicz

Gombodorj Bayarmagnai Department of Mathematics National University of Mongolia Baga Toirog Ulaanbaatar 14200 Mongolia

                  bayarmagnai@smcs.num.edu.mn

Abstract In 1961, Rotkiewicz presented a generalisation of the well-known fact that n divides φ(a^{n} − 1) for all positive integers n and a > 1, where φ is Euler’s totient function. In this note, we extend his result to values of cyclotomic polynomials.

1 Introduction

Let φ be the Euler’s totient function. It is well known that n | φ(a^{n} − 1) for all positive integers n and a > 1 (see, e.g., Gunderson [2]). Let Φ_{k} be the homogeneous cyclotomic polynomial of order k, and let d(n) be the number of divisors of n. Rotkiewicz [3] generalized the above result as follows:

n^{\frac{d(n)}{2}} | φ(Φ_{1}(a^{n}, b^{n}))

for all positive integers a, b (a > b) and n. In this note we extend this result to values of cyclotomic polynomials. Theorem 1. Let n and k be relatively prime positive integers. For all positive integers a, b (a > b) we have

k^{α}n^{\frac{d(n)}{2}} | φ(Φ_{k}(a^{n}, b^{n})),

where

α = \begin{cases}d(n) − 1, & if a = 2b and ke = 6 for some e | n; \\ d(n), & otherwise. \end{cases}

Note that the case of k = 2 was discussed in Rotkiewicz [3, Theorem 2].

Fix positive integers a, b (a > b) and k, and define a sequence (V_{n}^{(k)})_{n≥1} by setting V_{n}^{(k)} = Φ_{k}(a^{n}, b^{n}). Since Φ_{k} is homogeneous, we may assume without loss of generality that a and b are relatively prime.

For convenience, we recall the notion of arithmetic primitive factor introduced in Birkhoff-Vandiver [1] in the following way. A prime of V_{n}^{(k)} is called a primitive prime factor of the term if it does not divide any V_{m}^{(k)} for proper divisors m of n. We consider the arithmetic primitive factor of V_{n}^{(k)} given by the product

P_{n}^{(k)} = ∏_{p} p^{v_{p}(V_{n}^{(k)})},

where p runs through all primitive prime factors of the term. Here, v_{p}(n) denotes the exponent of p in the decomposition of n. If n and k are relatively prime then it follows from the identity

Φ_{k}(a^{n}, b^{n}) = ∏_{e|n} Φ_{ke}(a, b)  (1)

that P_{n}^{(k)} divides Φ_{kn}(a, b).

2 Proof

Let n be an integer relatively prime to a prime p, and let ord_{p}(n) be the order of n modulo p. We now state the following useful lemma.

Lemma 2. Let p be a prime not dividing b. Then

(a) v_{p}(Φ_{k}(a, b)) ≠ 0 if and only if k = p^{v_{p}(k)}ord_{p}(ab^{−1}),
(b) if v_{p}(k) ≠ 0 then v_{p}(Φ_{k}(a, b)) ≤ 1 (except k = p = 2).

Proof. See Roitman [4].

Proof of Theorem. Let d be a divisor of n. The identity (1) implies that every primitive prime of V_{kd}^{(1)} is a factor of P_{d}^{(k)}. Hence, by Zsigmondy’s theorem, P_{d}^{(k)} ≠ 1 if

(kd, a, b) ≠ (6, 2, 1).  (2)

Under the condition (2), we claim that P_{d}^{(k)} has a prime factor not dividing kd. Suppose that p is a prime of kd dividing Φ_{kd}(a, b). Then Lemma 2(a) implies that kd/p^{v_{p}(kd)} < p and so p is the largest prime of kd. Thus, by Lemma 2(b), p is the greatest common divisor of kd and Φ_{kd}(a, b). Hence, if the claim is not true, then it follows that P_{d}^{(k)} equals the largest prime of kd. Moreover, it also equals the primitive factor P_{kd}^{(1)}. But this contradicts to the fact that P_{n}^{(1)} is prime to p if the largest prime p of n is a factor of V_{n}^{(1)} (see Birkhoff-Vandiver [1, Theorem 4 ]).

Next we have that the primitive factors P_{d}^{(k)} are pairwise relatively prime. Indeed, if p is a factor of P_{d_{1}}^{(k)} and P_{d_{2}}^{(k)} then we may apply Lemma 2(a) to conclude that d_{1}/d_{2} is a power of p. Hence, p is not a primitive factor of one of V_{d_{1}}^{(k)} and V_{d_{2}}^{(k)}. This is a contradiction.

Assume that (2) holds for each factor d of n. Let q be a prime factor of P_{d}^{(k)} not dividing kd. Then it follows from Lemma 2(a) that kd | q − 1. Hence we obtain

k^{2}n | φ(P_{d}^{(k)})φ(P (k)_{\frac{n}{d}})  (3)

for each d such that n ≠ d^{2}. Thus, it is now clear that the factor ∏_{d|n} φ(P_{d}^{(k)}) of φ(V_{n}^{(k)}) is

divisible by k^{d(n)}n^{\frac{d(n)}{2}} .

It remains to consider only the case (kd, a, b) = (6, 2, 1) with d | n. In this case we have

P (k)_{\frac{6}{k}} = \begin{cases}1, & if k is 1 or 2; \\ 3, & otherwise. \end{cases}

Thus, (3) implies that kn| φ(P (k)_{\frac{6}{k}})φ(P (k)_{\frac{nk}{6}}) for k = 3, 6. When k = 2, we combine (3) with

the fact that 2^{3} + 1 | V_{n}^{(2)}. If k = 1 then P_{3}^{(1)} = 7 and so

n^{2}| φ(P_{3}^{(1)}P (1)_{\frac{n}{3}})φ(P (1)_{\frac{n}{6}})

as in the previous case. This completes the proof.

3 Acknowledgment

The author would like to thank the referee for carefully reading the paper and for some suggestions.

References

[1] G. D. Birkhoff and H. S. Vandiver, On the integral divisors of a^{n} − b^{n}, Ann. of Math. 5 (1904), 173–180.

[2] N. G. Gunderson, Some theorems on the Euler ϕ-function, Bull. Amer. Math. Soc. 49 (1943), 278–280.

[3] A. Rotkiewicz, On the numbers φ(a^{n} ± b^{n}), Proc. Amer. Math. Soc. 12 (1961), 419–421.

[4] M. Roitman, On Zsigmondy primes, Proc. Amer. Math. Soc. 125 (1997), 1913–1919.

2010 Mathematics Subject Classification: Primary 11A25; Secondary 11B83. Keywords: Euler’s totient function, primitive factor, cyclotomic polynomial.

Received November 25 2014; revised versions received February 4 2015; February 13 2015; February 14 2015. Published in Journal of Integer Sequences, February 14 2015.

Return to Journal of Integer Sequences home page.