##
**Numbers with small prime factors, and the least \(k\)-th power non-residue.**
*(English)*
Zbl 0211.37801

Mem. Am. Math. Soc. 106, 106 p. (1971).

Summary: For a positive integer \(n\) and real \(x,y\) with \(x\ge 1\), \(y\ge 0\), define \(\Psi_n(x,y)\) to be the number of integers \(m\) such that \(1\le m\le x\), \((m,n) = 1\), and \(m\) has no prime factor greater than \(y\). Define also \(B_l(n,x,y)\) to be the number of integers \(m\) such that \(1\le m\le x\), \(m\equiv l\pmod n\), and \(m\) has no prime factor greater than \(y\).

In §3, the author attempts a comprehensive review of previous research on the functions \(\Psi_n\) and \(B_l\). (One paper that was missed is [J. van de Lune and E. Wattel, Math. Centrum, Amsterdam Afd. Zuivere Wisk. ZW 1968-007, 35 p. (1968; Zbl 0215.06502)]. Errors are pointed out in several papers.

In §4, there is a more or less expository derivation (based on work of V. Ramaswami) of an asymptotic formula for \(B_l(n, x, x^{1/a})\), valid for \(1\le a\le (\log x)^{1/2}\) and \((l,n) =1\).

In §5, asymptotic formulas for \(\Psi_n(x,y)\)) are derived. For example,

\[ \Psi_n(x,x^{1/a}) = n^{-1} \varphi(n)\rho(a)x+ \varphi(n)b(n)\rho(a-1)(x/\log x) + \]

\[+ O\left( \{\rho(a - 3) \xi(n) + an/\varphi(n)\} (x/\log^2x) + 2^{\omega(n)}x^{(1 - 1/a)} \right) \]

whenever \(3 <a\le (\log x)^{1/2}\). Here \(\varphi(n)\) is Euler’s function, \(\omega(n)\) is the number of distinct prime factors of \(n\),

\[ b(n) = n^{-1} \left\{1 - \gamma - \sum_{p\mid n} (p-1)^{-1} \log p\right\}, \]

\(\gamma\) is Euler’s constant, \(\xi(n) = O(\{\log \log (3n)\}^3)\) and \(\rho(a)\) is a positive continuous non-increasing function defined recursively by \(\rho(a) = 1\) \(0\le a \le 1)\),

\[ \rho(a) = \rho(N) - \int_n^a v^{-1} \rho(v-1)\,dv\qquad (N < a \le N+1,\ N=1,2,\ldots). \]

In Theorem 5.55, an asymptotic formula is given for the number of integers \(m\) such that \(1\le m\le x\), \((m,n) = 1\), and \(C(n)\) has no prime factor greater than \(m^{1/a}\) \((a\) fixed, \(a >1)\). Let \(C(n)\) be the multiplicative group of residue classes mod \(n\) which are relatively prime to \(n\), let \(C_k(n)\) denote the subgroup of \(k\)-th powers, and write \(\nu_k(n) = [C(n) : C_k(n)]\).

In §6, results of the type (1) are used to get \(O\)-estimates for \(g_1(n,k)\) the smallest positive integer in \(C(n)\) but not in \(C_k(n)\). For example, let \(w)\) be any integer \(\ge 2\), and let \(a_w\) be the unique root of the equation \(\rho(a) = w^{-1}\). If \(n,k\) are any integers such that \(\nu_k(n)\ge w\), then for each \(\delta>0\),

\[ g_1(n,k) = O_{w,\delta} \left(n^{3/(8a_w) + \delta}\right), \]

the implied constant depending at most on \(w,\delta\). If a certain arithmetical condition on \(n\) and \(k\) is satisfied, then the exponent \(3/(8a_w)\) can be replaced by \(1/(4a_w)\). (With more effort, this arithmetical condition can be dispensed with, and we get, the result

\[ g_1(n,k) = O_{w,\delta} \left(n^{1/(4a_w) + \delta}\right), \]

whenever \(\nu_k(n)\ge w\). See a forthcoming paper by the author.)

In §7, several specific estimates are given for \(g_1(p,k)\) \((p\) prime), an example being

\[ g_1(p,k) \le 4.7p^{1/4}\log p\quad\text{for }(k,p -1) >1. \]

For large \(p\), this improves an inequality of it{A. Brauer} [Math. Z. 33, 161–176 (1931; Zbl 0001.05703)] for \(g_1(p,2)\) (Brauer’s result holds for \(p\equiv 7\pmod 8\); on p. 77 of the present paper, it is erroneously stated that he proved a similar result for \(p \equiv 1\pmod 8\).)

The paper concludes with a specific upper estimate for the number of distinct prime factors of \(n\).

In §3, the author attempts a comprehensive review of previous research on the functions \(\Psi_n\) and \(B_l\). (One paper that was missed is [J. van de Lune and E. Wattel, Math. Centrum, Amsterdam Afd. Zuivere Wisk. ZW 1968-007, 35 p. (1968; Zbl 0215.06502)]. Errors are pointed out in several papers.

In §4, there is a more or less expository derivation (based on work of V. Ramaswami) of an asymptotic formula for \(B_l(n, x, x^{1/a})\), valid for \(1\le a\le (\log x)^{1/2}\) and \((l,n) =1\).

In §5, asymptotic formulas for \(\Psi_n(x,y)\)) are derived. For example,

\[ \Psi_n(x,x^{1/a}) = n^{-1} \varphi(n)\rho(a)x+ \varphi(n)b(n)\rho(a-1)(x/\log x) + \]

\[+ O\left( \{\rho(a - 3) \xi(n) + an/\varphi(n)\} (x/\log^2x) + 2^{\omega(n)}x^{(1 - 1/a)} \right) \]

whenever \(3 <a\le (\log x)^{1/2}\). Here \(\varphi(n)\) is Euler’s function, \(\omega(n)\) is the number of distinct prime factors of \(n\),

\[ b(n) = n^{-1} \left\{1 - \gamma - \sum_{p\mid n} (p-1)^{-1} \log p\right\}, \]

\(\gamma\) is Euler’s constant, \(\xi(n) = O(\{\log \log (3n)\}^3)\) and \(\rho(a)\) is a positive continuous non-increasing function defined recursively by \(\rho(a) = 1\) \(0\le a \le 1)\),

\[ \rho(a) = \rho(N) - \int_n^a v^{-1} \rho(v-1)\,dv\qquad (N < a \le N+1,\ N=1,2,\ldots). \]

In Theorem 5.55, an asymptotic formula is given for the number of integers \(m\) such that \(1\le m\le x\), \((m,n) = 1\), and \(C(n)\) has no prime factor greater than \(m^{1/a}\) \((a\) fixed, \(a >1)\). Let \(C(n)\) be the multiplicative group of residue classes mod \(n\) which are relatively prime to \(n\), let \(C_k(n)\) denote the subgroup of \(k\)-th powers, and write \(\nu_k(n) = [C(n) : C_k(n)]\).

In §6, results of the type (1) are used to get \(O\)-estimates for \(g_1(n,k)\) the smallest positive integer in \(C(n)\) but not in \(C_k(n)\). For example, let \(w)\) be any integer \(\ge 2\), and let \(a_w\) be the unique root of the equation \(\rho(a) = w^{-1}\). If \(n,k\) are any integers such that \(\nu_k(n)\ge w\), then for each \(\delta>0\),

\[ g_1(n,k) = O_{w,\delta} \left(n^{3/(8a_w) + \delta}\right), \]

the implied constant depending at most on \(w,\delta\). If a certain arithmetical condition on \(n\) and \(k\) is satisfied, then the exponent \(3/(8a_w)\) can be replaced by \(1/(4a_w)\). (With more effort, this arithmetical condition can be dispensed with, and we get, the result

\[ g_1(n,k) = O_{w,\delta} \left(n^{1/(4a_w) + \delta}\right), \]

whenever \(\nu_k(n)\ge w\). See a forthcoming paper by the author.)

In §7, several specific estimates are given for \(g_1(p,k)\) \((p\) prime), an example being

\[ g_1(p,k) \le 4.7p^{1/4}\log p\quad\text{for }(k,p -1) >1. \]

For large \(p\), this improves an inequality of it{A. Brauer} [Math. Z. 33, 161–176 (1931; Zbl 0001.05703)] for \(g_1(p,2)\) (Brauer’s result holds for \(p\equiv 7\pmod 8\); on p. 77 of the present paper, it is erroneously stated that he proved a similar result for \(p \equiv 1\pmod 8\).)

The paper concludes with a specific upper estimate for the number of distinct prime factors of \(n\).

Reviewer: Karl K. Norton