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...

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 examine the congruences and iterate the digit sums of integer sequences. We generate recursive number sequences from triple and quintuple product identities. And we use second order recursions to determine the primality of special number systems.

En admettant la conjecture de Dickson, nous démontrons que, pour chaque couple d’entiers $q\>0$ et $k\>0$, il existe une partie infinie $L_{q,k}\subset \mathbb{N}$ telle que, pour chacun des entiers $n\in L_{q,k}$ et tout entier $s$ tel que $0\<\left|s\right|\le q$, on ait $n+s=\left|s\right|t_1...t_k$ où $t_1\<...\<t_k$ sont des nombres premiers. De même, pour chaque couple d’entiers $q\>0$ et $k\>0$, il existe une partie infinie $M_{q,k}\subset \mathbb{N}$ telle que, pour chacun des entiers $n\in M_{q,k}$ et tout entier $s$ (nul ou non ) de l’intervalle $\left[-q,q\right]$, on ait $n+s=l{t}_1...t_k$ où $t_1\<...\<t_k$ sont des nombres premiers et l’entier $l$ appartient à l’intervalle $\left[1,2q+1\right]$. La lecture non standard...

Le problème de la primalité est l’un des problèmes les plus simples et les plus anciens de la théorie des nombres. À la fin des années 1970, Adleman, Pomerance et Rumely ont donné le premier algorithme de primalité déterministe, dont le temps de calcul était presque polynomial. Il a fallu 20 années supplémentaires pour qu’Agrawal, Kayal et Saxena donnent un algorithme déterministe de temps de calcul polynomial. L’exposé présentera ces travaux, et il fera également le point sur les différents autres...

We assign to each positive integer $n$ a digraph whose set of vertices is $H=\{0,1,\cdots ,n-1\}$ and for which there is a directed edge from $a\in H$ to $b\in H$ if $a^2\equiv b\left(modn\right)$. We establish necessary and sufficient conditions for the existence of isolated fixed points. We also examine when the digraph is semiregular. Moreover, we present simple conditions for the number of components and length of cycles. Two new necessary and sufficient conditions for the compositeness of Fermat numbers are also introduced.

Given an integer $n\ge 3$, let $u_1,...,u_n$ be pairwise coprime integers $\ge 2$, $𝒟$ a family of nonempty proper subsets of $\{1,...,n\}$ with “enough” elements, and $\epsilon$ a function $𝒟\to \{\pm 1\}$. Does there exist at least one prime $q$ such that $q$ divides ${\prod }_{i\in I}{u}_i-\epsilon \left(I\right)$ for some $I\in 𝒟$, but it does not divide $u_1\cdots u_n$? We answer this question in the positive when the $u_i$ are prime powers and $\epsilon$ and $𝒟$ are subjected to certain restrictions.We use the result to prove that, if ${\epsilon }_0\in \{\pm 1\}$ and $A$ is a set of three or more primes that contains all prime divisors of any number of the form ${\prod }_{p\in B}p-{\epsilon }_0$ for...