Exponents of primes in generalized binomial coefficients.
Expressing rationals as a sum of a small number of unit fractions
Extended Euclidean Algorithm and CRT Algorithm
In this article we formalize some number theoretical algorithms, Euclidean Algorithm and Extended Euclidean Algorithm [9]. Besides the a gcd b, Extended Euclidean Algorithm can calculate a pair of two integers (x, y) that holds ax + by = a gcd b. In addition, we formalize an algorithm that can compute a solution of the Chinese remainder theorem by using Extended Euclidean Algorithm. Our aim is to support the implementation of number theoretic tools. Our formalization of those algorithms is based...
Extended GCD and Hermite normal form algorithms via lattice basis reduction.
Extension aux nombres premiers complexes des théorèmes de M. Tchebicheff
Extensions of Bauer's identical congruences
Extensions of the Gauss-Wilson theorem.
Facteurs premiers des coefficients binomiaux
Factor tables 1657–1817, with notes on the birth of number theory
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...
Factoring and testing primes in small space
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...
Factoring integers with large-prime variations of the quadratic sieve.
Factorisation de fractions rationnelles et de suites récurrentes
Factorisation des polynômes à plusieurs variables à coefficients entiers
Factorization of matrices associated with classes of arithmetical functions
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 having f evaluated at the greatest common divisor of and as its...
Factors of a perfect square
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 and .
Families of rational numbers with predictable Engel product expansions.
Farey fractions and sums over coprime pairs
Farhi arithmetic functions associated to Lucas sequences
Fermat and Wilson quotients for -adic integers
Fermat test with Gaussian base and Gaussian pseudoprimes
The structure of the group 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 . In particular, we characterize Gaussian Carmichael numbers...