The history of the construction, organisation and publication of factor tables from 1657 to 1817, in itself a fascinating story, also touches upon many topics of general interest for the history of mathematics. The considerable labour involved in constructing and correcting these tables has pushed mathematicians and calculators to organise themselves in networks. Around 1660 J. Pell was the first to motivate others to calculate a large factor table, for which he saw many applications, from Diophantine...

We discuss how much space is sufficient to decide whether a unary given number n is a prime. We show that O(log log n) space is sufficient for a deterministic Turing machine, if it is equipped with an additional pebble movable along the input tape, and also for an alternating machine, if the space restriction applies only to its accepting computation subtrees. In other words, the language is a prime is in pebble–DSPACE(log log n) and also in accept–ASPACE(log log n). Moreover, if the given n is...

Let f be an arithmetical function. A set S = x₁,..., xₙ of n distinct positive integers is called multiple closed if y ∈ S whenever x|y|lcm(S) for any x ∈ S, where lcm(S) is the least common multiple of all elements in S. We show that for any multiple closed set S and for any divisor chain S (i.e. x₁|...|xₙ), if f is a completely multiplicative function such that (f*μ)(d) is a nonzero integer whenever d|lcm(S), then the matrix $\left(f(x_i,x_i)\right)$ having f evaluated at the greatest common divisor $(x_i,x_i)$ of $x_i$ and $x_i$ as its...

We consider a conjecture of Erdős and Rosenfeld and a conjecture of Ruzsa when the number is a perfect square. In particular, we show that every perfect square n can have at most five divisors between $\surd n-∜n{\left(logn\right)}^{1/7}$ and $\surd n+∜n{\left(logn\right)}^{1/7}$.

The structure of the group ${(\mathbb{Z}/n\mathbb{Z})}^{☆}$ and Fermat’s little theorem are the basis for some of the best-known primality testing algorithms. Many related concepts arise: Euler’s totient function and Carmichael’s lambda function, Fermat pseudoprimes, Carmichael and cyclic numbers, Lehmer’s totient problem, Giuga’s conjecture, etc. In this paper, we present and study analogues to some of the previous concepts arising when we consider the underlying group ${𝒢}_n:=\{a+b\mathrm{i}\in \mathbb{Z}\left[\mathrm{i}\right]/n\mathbb{Z}\left[\mathrm{i}\right]:a^2+b^2\equiv 1(modn)\}$. In particular, we characterize Gaussian Carmichael numbers...

Solving equations in integers is an important part of the number theory [29]. In many cases it can be conducted by the factorization of equation’s elements, such as the Newton’s binomial. The article introduces several simple formulas, which may facilitate this process. Some of them are taken from relevant books [28], [14]. In the second section of the article, Fermat’s Little Theorem is proved in a classical way, on the basis of divisibility of Newton’s binomial. Although slightly redundant in...

We show that if m > 1 is a Fibonacci number such that ϕ(m) | m-1, where ϕ is the Euler function, then m is prime

For $\mathbf{r}=(r_0,...,r_{d-1})\in {ℝ}^d$ define the function$${\tau }_{\mathbf{r}}:{\mathbb{Z}}^d\to {\mathbb{Z}}^d,\mathbf{z}=(z_0,...,z_{d-1})\mapsto (z_1,...,z_{d-1},-⌊\mathbf{rz}⌋),$$where $\mathbf{rz}$ is the scalar product of the vectors $\mathbf{r}$ and $\mathbf{z}$. If each orbit of ${\tau }_{\mathbf{r}}$ ends up at $\mathbf{0}$, we call ${\tau }_{\mathbf{r}}$ a shift radix system. It is a well-known fact that each orbit of ${\tau }_{\mathbf{r}}$ ends up periodically if the polynomial $t^d+r_{d-1}{t}^{d-1}+\cdots +r_0$ associated to $\mathbf{r}$ is contractive. On the other hand, whenever this polynomial has at least one root outside the unit disc, there exist starting vectors that give rise to unbounded orbits. The present paper deals with the remaining situations of periodicity properties of...