We give upper and lower bounds on the count of positive integers n ≤ x dividing the nth term of a non-degenerate linearly recurrent sequence with simple roots.

Let q be an odd prime. In this paper, we prove that if N is an odd perfect number with qα∥N then σ(N/qα)/qα≠p,p2,p3,p4,p1p2,p21p2, where p,p1, p2 are primes and p1≠p2. This improves a result of Dris and Luca [‘A note on odd perfect numbers’, arXiv:1103.1437v3 [math.NT]]: σ(N/qα)/qα≠1,2,3,4,5. Furthermore, we prove that for K≥1 , if N is an odd perfect number with qα ∥N and σ(N/qα)/qα ≤K, then N≤4K8.

In 1987, Gordon gave an integer primality condition similar to the familiar test based on Fermat’s little theorem, but based instead on the arithmetic of elliptic curves with complex multiplication. We prove the existence of infinitely many composite numbers simultaneously passing all elliptic curve primality tests assuming a weak form of a standard conjecture on the bound on the least prime in (special) arithmetic progressions. Our results are somewhat more general than both the 1999 dissertation of the first author (written under the direction of the third author) and a 2010 paper on Carmichael numbers in a residue class written by Banks and the second author.

We describe a variant of Fermat’s factoring algorithm which is competitive with SQUFOF in practice but has heuristic run time complexity O(n1/3) as a general factoring algorithm. We also describe a sparse class of integers for which the algorithm is particularly effective. We provide speed comparisons between an optimised implementation of the algorithm described and the tuned assortment of factoring algorithms in the Pari/GP computer algebra package.

For a primitive root g modulo a prime p≥1 we obtain upper bounds on the gaps between the residues modulo p of the N consecutive powers agn, n=1,…,N, which is uniform over all integers a with gcd (a,p)=1.

In this paper we give an extension of a curious combinatorial identity due to B. Sury. Our proof is very simple and elementary. As an application, we obtain two congruences for Fermat quotients modulo p3. Moreover, we prove an extension of a result by H. Pan that generalizes Carlitz’s congruence.

Let k≥2 be an integer. A natural number n is called k-perfect if σ(n)=kn. For any integer r≥1, we prove that the number of odd k-perfect numbers with at most r distinct prime factors is bounded by (k−1)4r3.

In this paper we derive congruences expressing Bell numbers and derangement numbers in terms of each other modulo any prime.

Starting with a paper of Jacobson from the 1960s, many authors became interested in characterizing all algebraic number fields in which each integer is the sum of pairwise distinct units. Although there exist many partial results for number fields of low degree, a full characterization of these number fields is still not available. Narkiewicz and Jarden posed an analogous question for sums of units that are not necessarily distinct. In this paper we propose a generalization of these problems. In particular, for a given rational integer n we consider the following problem. Characterize all number fields for which every integer is a linear combination of finitely many units εi in a way that the coefficients ai∈ℕ are bounded by n. The paper gives several partial results on this problem. In our proofs we exploit the fact that these representations are related to symmetric beta expansions with respect to Pisot bases.

Let k ≥ 0, a ≥ 1 and b ≥ 0 be integers. We define the arithmetic function gk,a,b for any positive integer n by

If we let a = 1 and b = 0, then gk,a,b becomes the arithmetic function that was previously introduced by Farhi. Farhi proved that gk,1,0 is periodic and that k! is a period. Hong and Yang improved Farhi's period k! to lcm(1, 2, … , k) and conjectured that (lcm(1, 2, … , k, k + 1))/(k + 1) divides the smallest period of gk,1,0. Recently, Farhi and Kane proved this conjecture and determined the smallest period of gk,1,0. For the general integers a ≥ 1 and b ≥ 0, it is natural to ask the following interesting question: is gk,a,b periodic? If so, what is the smallest period of gk,a,b? We first show that the arithmetic function gk,a,b is periodic. Subsequently, we provide detailed p-adic analysis of the periodic function gk,a,b. Finally, we determine the smallest period of gk,a,b. Our result extends the Farhi–Kane Theorem from the set of positive integers to general arithmetic progressions.

Given a prime p, the Fermat quotient qp(u) of u with gcd (u,p)=1 is defined by the conditions We derive a new bound on multiplicative character sums with Fermat quotients qp(ℓ) at prime arguments ℓ.

Erdős and Szekeres [‘Some number theoretic problems on binomial coefficients’, Aust. Math. Soc. Gaz.5 (1978), 97–99] showed that for any four positive integers satisfying m1+m2=n1+n2, the two binomial coefficients (m1+m2)!/m1!m2! and (n1+n2)!/n1!n2! have a common divisor greater than 1. The analogous statement for k-element families of k-nomial coefficients (k>1) was conjectured in 1997 by David Wasserman.

Erdős and Szekeres remark that if m1,m2,n1,n2 as above are all greater than 1, there is probably a lower bound on the common divisor in question which goes to infinity as a function of m1 +m2 . Such a bound is obtained in Section 2.

The remainder of this paper is devoted to proving results that narrow the class of possible counterexamples to Wasserman’s conjecture.

Assuming a conjecture intermediate in strength between one of Chowla and one of Heath-Brown on the least prime in a residue class, we show that for any coprime integers a and m≥1, there are infinitely many Carmichael numbers in the arithmetic progression a mod m.

Given a finite field 𝔽p={0,…,p−1} of p elements, where p is a prime, we consider the distribution of elements in the orbits of a transformation ξ↦ψ(ξ) associated with a rational function ψ∈𝔽p(X). We use bounds of exponential sums to show that if N≥p1/2+ε for some fixed ε then no N distinct consecutive elements of such an orbit are contained in any short interval, improving the trivial lower bound N on the length of such intervals. In the case of linear fractional functions we use a different approach, based on some results of additive combinatorics due to Bourgain, that gives a nontrivial lower bound for essentially any admissible value of N.

Let 〈𝒫〉⊂N be a multiplicative subsemigroup of the natural numbers N={1,2,3,…} generated by an arbitrary set 𝒫 of primes (finite or infinite). We give an elementary proof that the partial sums ∑ n∈〈𝒫〉:n≤x(μ(n))/n are bounded in magnitude by 1. With the aid of the prime number theorem, we also show that these sums converge to ∏ p∈𝒫(1−(1/p)) (the case where 𝒫 is all the primes is a well-known observation of Landau). Interestingly, this convergence holds even in the presence of nontrivial zeros and poles of the associated zeta function ζ𝒫(s)≔∏ p∈𝒫(1−(1/ps))−1 on the line {Re(s)=1}. As equivalent forms of the first inequality, we have ∣∑ n≤x:(n,P)=1(μ(n))/n∣≤1, ∣∑ n∣N:n≤x(μ(n))/n∣≤1, and ∣∑ n≤x(μ(mn))/n∣≤1 for all m,x,N,P≥1.

For a natural number n, let λ(n) denote the order of the largest cyclic subgroup of (ℤ/nℤ)*. For a given integer a, let Na(x) denote the number of n ≤ x coprime to a for which a has order λ(n) in (ℤ/nℤ)*. Let R(n) denote the number of elements of (ℤ/nℤ)* with order λ(n). It is natural to compare Na(x) with ∑n≤xR(n)/n. In this paper we show that the average of Na(x) for 1 ≤ a ≤ y is indeed asymptotic to this sum, provided y ≥ exp((2 + ε)(log x log log x)1/2), thus improving a theorem of the first author who had this for y ≥ exp((log x)3/4;). The result is to be compared with a similar theorem of Stephens who considered the case of prime numbers n.

Let 𝒜={as(mod ns)}ks=0 be a system of residue classes. With the help of cyclotomic fields we obtain a theorem which unifies several previously known results related to the covering multiplicity of 𝒜. In particular, we show that if every integer lies in more than m0=⌊∑ ks=11/ns⌋ members of 𝒜, then for any a=0,1,2,… there are at least subsets I of {1,…,k} with ∑ s∈I1/ns=a/n0. We also characterize when any integer lies in at most m members of 𝒜, where m is a fixed positive integer.

Browkin [‘Some new kinds of pseudoprimes’, Math. Comp. 73 (2004), 1031–1037] gave examples of strong pseudoprimes to many bases which are not Sylow p-pseudoprimes to two bases only, where p=2 or 3. In contrast to Browkin’s examples, Zhang [‘Notes on some new kinds of pseudoprimes’, Math. Comp. 75 (2006), 451–460] gave facts and examples which are unfavorable for Browkin’s observation on detecting compositeness of odd composite numbers. In particular, Zhang gave a Sylowp-pseudoprime (with 27 decimal digits) to the first 6 prime bases for all the first 6 primes p, and conjectured that for any k≥1, there would exist Sylow p-pseudoprimes to the first k prime bases for all the first k primes p. In this paper we tabulate 27 Sylow p-pseudoprimes less than 1036 to the first 7 prime bases for all the first 7 primes p (two of which are Sylow p-pseudoprimes to the first 7 prime bases for all the first 8 primes p). We describe the procedure for finding these numbers. The main tools used in our method are the cubic residue characters and the Chinese remainder theorem.

A number is called upper (lower) flat if its shift by +1 ( −1) is a power of 2 times a squarefree number. If the squarefree number is 1 or a single odd prime then the original number is called upper (lower) thin. Upper flat numbers which are primes arise in the study of multi-perfect numbers. Here we show that the lower or upper flat primes have asymptotic density relative to that of the full set of primes given by twice Artin’s constant, that more than 53% of the primes are both lower and upper flat, and that the series of reciprocals of the lower or the upper thin primes converges.

The main goal of this paper is to provide asymptotic expansions for the numbers #{p≤x:p prime,sq(p)=k} for k close to ((q−1)/2)log qx, where sq(n) denotes the q-ary sum-of-digits function. The proof is based on a thorough analysis of exponential sums of the form (where the sum is restricted to p prime), for which we have to extend a recent result by the second two authors.