Search

We extend the Siegel-Walfisz theorem to a family of integer sequences that are characterized by constraints on the size of the prime factors. Besides prime powers, this family includes smooth numbers, almost primes and practical numbers., 11 pages

Watkins conjectured that for an elliptic curve $E$ over $\mathbb{Q}$ of Mordell-Weil rank $r$, the modular degree of $E$ is divisible by $2^r$. If $E$ has non-trivial rational $2$-torsion, we prove the conjecture for all the quadratic twists of $E$ by squarefree integers with sufficiently many prime factors.

Given a function field $K$ and $\phi \in K[x]$, we study two finiteness questions related to iteration of $\phi$: whether all but finitely many terms of an orbit of $\phi$ must possess a primitive prime divisor, and whether the Galois groups of iterates of $\phi$ must have finite index in their natural overgroup $\text{Aut}(T_d)$, where $T_d$ is the infinite tree of iterated preimages of $0$ under $\phi$. We focus particularly on the case where $K$ has characteristic $p$, where far less is known. We resolve the first question in the affirmative under relatively weak hypotheses; interestingly, the main step in our proof is to rule out "Riccati differential equations" in backwards orbits. We then apply our result on primitive prime divisors and adapt a method of Looper to produce a family of polynomials for which the second question has an affirmative answer; these are the first non-isotrivial examples of such polynomials. We also prove that almost all quadratic polynomials over $\mathbb{Q}(t)$ have iterates whose Galois group is all of $\text{Aut}(T_d)$.

International audience; In this work, we consider the proportion of smooth (free of large prime factors) values of a binary form $F(X_1,X_2)\in\mathbf{Z}[X_1,X_2]$. In a particular case, we give an asymptotic equivalent for this proportion which depends on $F$. This is related to Murphy's $\alpha$ function, which is known in the cryptographic community, but which has not been studied before from a mathematical point of view. Our result proves that, when $\alpha(F)$ is small, $F$ has a high proportion of smooth values. This has consequences on the first step, called polynomial selection, of the Number Field Sieve, the fastest algorithm of integer factorization.; Dans cet article, nous étudions la proportion de valeurs friables (sans grands facteurs premiers) d'une forme binaire $F(X_1,X_2)\in\mathbf{Z}[X_1,X_2]$. Dans un cas particulier, nous prouvons un équivalent asymptotique de cette proportion qui dépend de $F$. Cela est lié à la fonction $\alpha$ de Murphy, qui est connu à la communauté cryptographique, mais qui n'a pas été étudiée précédemment avec des outils mathématiques. Notre résultat montre que, si $\alpha(F)$ est petit, alors $F$ a un grand nombre de valeurs friables. Cela a des conséquences sur la première étape, appelée sélection polynomiale, du crible algébrique (NFS), meilleur algorithme de factorisation d'entiers.

We present a (random) polynomial-time algorithm to generate a random Gauss- ian integer with the uniform distribution among those with norm at most N, along with its prime factorization. The method generalizes to finding a random ideal in the ring of integers of a quadratic number field together with its prime ideal factorization. We also discuss the analogous problem for higher degree number fields.

The strong probable primality test is an important practical tool for discovering prime numbers. Its effectiveness derives from the following fact: for any odd composite number $n$, if a base $a$ is chosen at random, the algorithm is unlikely to claim that $n$ is prime. If this does happen we call $a$ a liar. In 1986, Erd\H{o}s and Pomerance computed the normal and average number of liars, over all $n \leq x$. We continue this theme and use a variety of techniques to count $n \leq x$ with exactly two strong liars, those being the $n$ for which the strong test is maximally effective. We evaluate this count asymptotically and give an improved algorithm to determine it exactly. We also provide asymptotic counts for the restricted case in which $n$ has two prime factors, and for the $n$ with exactly two Euler liars.

The generalized Fitting height of a finite group $G$ is the least number $h=h^*(G)$ such that $F^*_h(G)=G$, where the $F^*_i(G)$ is the generalized Fitting series: $F^*_1(G)=F^*(G)$ and $F^*_{i+1}(G)$ is the inverse image of $F^*(G/F^*_{i}(G))$. It is proved that if $G$ admits a soluble group of automorphisms $A$ of coprime order, then $h^*(G)$ is bounded in terms of $h^* (C_G(A))$, where $C_G(A)$ is the fixed-point subgroup, and the number of prime factors of $|A|$ counting multiplicities. The result follows from the special case when $A=\langle\varphi\rangle$ is of prime order, where it is proved that $F^*(C_G(\varphi ))\leqslant F^*_{9}(G)$. The nonsoluble length $\lambda (G)$ of a finite group $G$ is defined as the minimum number of nonsoluble factors in a normal series each of whose factors either is soluble or is a direct product of nonabelian simple groups. It is proved that if $A$ is a group of automorphisms of $G$ of coprime order, then $\lambda (G)$ is bounded in terms of $\lambda (C_G(A))$ and the number of prime factors of $|A|$ counting multiplicities.

International audience; Let ω(n) and Ω(n) denote, respectively, the total number of prime factors and the number of distinct prime factors of the integer n. Euler proved that an odd perfect number N is of the form N = pᶱm² where p ≡ e ≡ 1 (mod 4), p is prime, and p ∤ m. This implies that Ω(N) ≥ 2ω(N) − 1. We. We prove that Ω(N) ≥ (18ω(N) −31) /7andΩ(N) ≥ 2ω(N) + 51.

We have constructed a Carmichael number with 10,333,229,505 prime factors, and have also constructed Carmichael numbers with k prime factors for every k between 3 and 19,565,220. These computations are the product of implementations of two new algorithms for the subset product problem that exploit the non-uniform distribution of primes p with the property that p-1 divides a highly composite \Lambda., Comment: Table 1 fixed; previously the last 30 digits and number of digits were calculated incorrectly

For a fixed prime $p$, let $e_p(n!)$ denote the order of $p$ in the prime factorization of $n!$. Chen and Liu (2007) asked whether for any fixed $m$, one has $\{e_p(n^2!) \bmod m:\; n\in\mathbb{Z}\}=\mathbb{Z}_m$ and $\{e_p(q!) \bmod m:\; q {prime}\}=\mathbb{Z}_m$. We answer these two questions and show asymptotic formulas for $# \{n, Comment: 9 pages

The generalized wreath product of permutation groups is introduced. By means of it we study the schurity problem for S-rings over a cyclic group G and the automorphism groups of them. Criteria for the schurity and non-schurity of the generalized wreath product of two such S-rings are obtained. As a byproduct of the developed theory we prove that G is a Schur group whenever the total number Ω(n) of prime factors of the integer n = |G| is at most 3. Moreover, we describe the structure of a non-schurian S-ring over G when Ω(n) = 4. The latter result implies in particular that if n = p3q where p and q are primes, then G is a Schur group.

In this paper, we find all integers $x$ such that $x^{2}-1$ has only prime factors smaller than 100. This gives some interesting numerical corollaries. For example, for any positive integer $n$ we can find the largest positive integer $x$ such that all prime factors of each of $x, x+1,..., x+n$ are less than 100., 10 pages, to appear in Math. Comp

We discuss the numbers in the title, and in particular whether the minimum period of the Bell numbers modulo a prime p can be a proper divisor of Np = (p P — 1)/(p - 1). It is known that the period always divides Np. The period is shown to equal Np for most primes p below 180. The investigation leads to interesting new results about the possible prime factors of Np. For example, we show that if p is an odd positive integer and m is a positive integer and q = 4m 2 p + 1 is prime, then q divides p m2p - 1. Then we explain how this theorem influences the probability that q divides Np.

A general method of estimating the number of oscillations of a given size of arithmetic error terms is developed. Special attention is paid to the remainder terms in the prime number formula, in the Dirichlet prime number theorem for primes in arithmetic progressions and to the remainder term in the asymptotic formula for the number of square free divisors of an integer.

Let ω ( n ) \omega (n) be the number of distinct prime factors of n n . For any positive integer k k let n = n k n=n_k be the smallest positive integer such that ω ( n + 1 ) , … , ω ( n + k ) \omega (n+1),\ldots ,\omega (n+k) are mutually distinct. In this paper, we give upper and lower bounds for n k n_k . We study the same quantity when ω ( n ) \omega (n) is replaced by Ω ( n ) \Omega (n) , the total number of prime factors of n n counted with repetitions.

We discuss the distinctness problem of the reductions modulo M of maximal length sequences modulo powers of an odd prime p, where the integer M has a prime factor different from p. For any two different maximal length sequences generated by the same polynomial, we prove that their reductions modulo M are distinct. In other words, the reduction modulo M of a maximal length sequence is proved to contain all the information of the original sequence.

Jenkins in 2003 showed that every odd perfect number is divisible by a prime exceeding 10 7 . Using the properties of cyclotomic polynomials, we improve this result to show that every perfect number is divisible by a prime exceeding 10 8 .

This note contains a new algorithm for computing a function f(k) introduced by Erdos to measure the minimal gap size in the sequence of integers at least one of whose prime factors exceeds k. This algorithm enables us to show that f(k) is not monotone, verifying a conjecture of Ecklund and Eggleton.

Let A 3 be the set of all positive integers pqr, where p,q,r are primes and possibly two, but not all three of them are equal. For any n = pqr ∈ A 3 , define a function w by w(n) = P(p + q)P(p + r)P(q + r), where P(m) is the largest prime factor of m. It is clear that if n = pqr ∈ A 3 , then w(n) ∈ A 3 . For any n ∈ A 3 , define w°(n) = n, w i (n) = w(w i-1 (n)) for i = 1, 2,.... An element n ∈ A 3 is semi-periodic if there exists a nonnegative integer s and a positive integer t such that w s+t (n) = w s (n). We use ind(n) to denote the least such nonnegative integer s. Wushi Goldring [Dynamics of the w function and primes, J. Number Theory 119(2006), 86-98] proved that any element n ∈ A 3 is semi-periodic. He showed that there exists i such that w i (n) ∈ {20,98,63,75}, ind(n) ≤ 4(π(P(n)) - 3), and conjectured that ind(n) can be arbitrarily large. In this paper, it is proved that for any n ∈ A 3 we have ind(n) = O((logP(n)) 2 ), and the Green-Tao Theorem on arithmetic progressions in the primes is employed to confirm Goldring's above conjecture.

Via the cut-and-stack construction we produce a 2-fold simple ng transformation which has countably many proper factors and weakly mixing transformation which has countably many proper factors and all of them are 2-to-1 and prime.

Let $\sigma(n)$ denote the sum of the positive divisors of $n$. We say that $n$ is perfect if $\sigma(n) = 2 n$. Currently there are no known odd perfect numbers. It is known that if an odd perfect number exists, then it must be of the form $N = p^\alpha \prod_{j=1}^k q_j^{2 \beta_j}$, where $p, q_1, ..., q_k$ are distinct primes and $p \equiv \alpha\equiv 1 \pmod{4}$. Define the total number of prime factors of $N$ as $\Omega(N) := \alpha + 2 \sum_{j=1}^k \beta_j$. Sayers showed that $\Omega(N) \geq 29$. This was later extended by Iannucci and Sorli to show that $\Omega(N) \geq 37$. This was extended by the author to show that $\Omega(N) \geq 47$. Using an idea of Carl Pomerance this paper extends these results. The current new bound is $\Omega(N) \geq 75$., Comment: 9 pages

Let n > 1 be an odd composite integer. Write n - 1 = 2 s d with d odd. If either b d ≡ 1 mod n or b 2r d ≡ -1 mod n for some r = 0,1,..., s - 1, then we say that n is a strong pseudoprime to base b, or spsp(b) for short. Define ψ t to be the smallest strong pseudoprime to all the first t prime bases. If we know the exact value of ψ t , we will have, for integers n 10 36 ; and to give reasons and numerical evidence of K2- and C 3 -spsp's 12, where ψ' t (resp. ψ" t ) is the smallest K2- (resp. C 3 -) strong pseudoprime to all the first t prime bases. For this purpose we describe procedures for computing and enumerating the two kinds of spsp's < 10 36 to the first 9 prime bases. The entire calculation took about 4000 hours on a PC Pentium IV/1.8GHz. (Recall that a K2-spsp is an spsp of the form: n = pq with p, q primes and q - 1 = 2(p - 1); and that a C 3 -spsp is an spsp and a Carmichael number of the form: n = q 1 q 2 q 3 with each prime factor q i = 3 mod 4.).

A positive integer is called a (Ore's) harmonic number if its positive divisors have integral harmonic mean. Ore conjectured that every harmonic number greater than 1 is even. If Ore's conjecture is true, there exist no odd perfect numbers. In this paper, we prove that every odd harmonic number greater than 1 must be divisible by a prime greater than 10 5 .

Ψ ( x , y ) \Psi (x,y) denotes the number of positive integers ≤ x \leq x and free of prime factors > y >y . Hildebrand and Tenenbaum gave a smooth approximation formula for Ψ ( x , y ) \Psi (x,y) in the range ( log ⁡ x ) 1 + ϵ > y ≤ x (\log x)^{1+\epsilon }> y \leq x , where ϵ \epsilon is a fixed positive number ≤ 1 / 2 \leq 1/2 . In this paper, by modifying their approximation formula, we provide a fast algorithm to approximate Ψ ( x , y ) \Psi (x,y) . The computational complexity of this algorithm is O ( ( log ⁡ x ) ( log ⁡ y ) ) O(\sqrt {(\log x)(\log y)}) . We give numerical results which show that this algorithm provides accurate estimates for Ψ ( x , y ) \Psi (x,y) and is faster than conventional methods such as algorithms exploiting Dickman’s function.

J. Browkin defined in his recent paper (Math. Comp. 73 (2004), pp. 1031–1037) some new kinds of pseudoprimes, called Sylow p p -pseudoprimes and elementary Abelian p p -pseudoprimes. He gave examples of strong pseudoprimes to many bases which are not Sylow p p -pseudoprime to two bases only, where p = 2 p=2 or 3 3 . In this paper, in contrast to Browkin’s examples, we give facts and examples which are unfavorable for Browkin’s observation to detect compositeness of odd composite numbers. In Section 2, we tabulate and compare counts of numbers in several sets of pseudoprimes and find that most strong pseudoprimes are also Sylow 2 2 -pseudoprimes to the same bases. In Section 3, we give examples of Sylow p p -pseudoprimes to the first several prime bases for the first several primes p p . We especially give an example of a strong pseudoprime to the first six prime bases, which is a Sylow p p -pseudoprime to the same bases for all p ∈ { 2 , 3 , 5 , 7 , 11 , 13 } p\in \{2,3,5,7,11,13\} . In Section 4, we define n n to be a k k -fold Carmichael Sylow pseudoprime, if it is a Sylow p p -pseudoprime to all bases prime to n n for all the first k k smallest odd prime factors p p of n − 1 n-1 . We find and tabulate all three 3 3 -fold Carmichael Sylow pseudoprimes > 10 16 >10^{16} . In Section 5, we define a positive odd composite n n to be a Sylow uniform pseudoprime to bases b 1 , … , b k b_1,\ldots ,b_k , or a Syl-upsp ( b 1 , … , b k ) (b_1,\ldots ,b_k) for short, if it is a Syl p _p -psp ( b 1 , … , b k ) (b_1,\ldots ,b_k) for all the first ω ( n − 1 ) − 1 \omega (n-1)-1 small prime factors p p of n − 1 n-1 , where ω ( n − 1 ) \omega (n-1) is the number of distinct prime factors of n − 1 n-1 . We find and tabulate all the 17 Syl-upsp ( 2 , 3 , 5 ) (2,3,5) ’s > 10 16 >10^{16} and some Syl-upsp ( 2 , 3 , 5 , 7 , 11 ) (2,3,5,7,11) ’s > 10 24 >10^{24} . Comparisons of effectiveness of Browkin’s observation with Miller tests to detect compositeness of odd composite numbers are given in Section 6.

Let p denote a prime. In this article we provide the first published lower bounds for the greatest prime factor of p - I exceeding (p - 1) 1 /2 in which the constants are effectively computable. As a result we prove that it is possible to calculate a value x 0 such that for every x > x 0 there is a p < x with the greatest prime factor of p - 1 exceeding x 3/5 . The novelty of our approach is the avoidance of any appeal to Siegel's Theorem on primes in arithmetic progression.

Let q 1 > q 2 > q 3 q_1>q_2>q_3 be odd primes and N = q 1 q 2 q 3 N=q_1q_2q_3 . Put \[ d = gcd ( q 1 − 1 , q 2 − 1 , q 3 − 1 ) and h i = q i − 1 d , i = 1 , 2 , 3. d=\gcd (q_1-1,q_2-1,q_3-1) \text { and } h_i=\tfrac {q_i-1}d, \;i=1,2,3. \] Then we call d d the kernel, the triple ( h 1 , h 2 , h 3 ) (h_1,h_2,h_3) the signature, and H = h 1 h 2 h 3 H=h_1h_2h_3 the height of N N , respectively. We call N N a C 3 C_3 -number if it is a Carmichael number with each prime factor q i ≡ 3 mod 4 q_i\equiv 3\mod 4 . If N N is a C 3 C_3 -number and a strong pseudoprime to the t t bases b i b_i for 1 ≤ i ≤ t 1\leq i\leq t , we call N N a C 3 C_3 -spsp ( b 1 , b 2 , … , b t ) (b_1, b_2,\dots ,b_t) . Since C 3 C_3 -numbers have probability of error 1 / 4 1/4 (the upper bound of that for the Rabin-Miller test), they often serve as the exact values or upper bounds of ψ m \psi _m (the smallest strong pseudoprime to all the first m m prime bases). If we know the exact value of ψ m \psi _m , we will have, for integers n > ψ m n>\psi _m , a deterministic efficient primality testing algorithm which is easy to implement. In this paper, we first describe an algorithm for finding C 3 C_3 -spsp(2)’s, to a given limit, with heights bounded. There are in total 21978 21978 C 3 C_3 -spsp ( 2 ) (2) ’s > 10 24 >10^{24} with heights > 10 9 >10^9 . We then give an overview of the 21978 C 3 C_3 - spsp(2)’s and tabulate 54 54 of them, which are C 3 C_3 -spsp’s to the first 8 8 prime bases up to 19 19 ; three numbers are spsp’s to the first 11 prime bases up to 31. No C 3 C_3 -spsp’s > 10 24 >10^{24} to the first 12 12 prime bases with heights > 10 9 >10^9 were found. We conjecture that there exist no C 3 C_3 -spsp’s > 10 24 >10^{24} to the first 12 12 prime bases with heights ≥ 10 9 \geq 10^9 and so that ψ 12 a m p ; = 3186 65857 83403 11511 67461 (24 digits) a m p ; = 399165290221 ⋅ 798330580441 , \begin{equation*} \begin {split} \psi _{12}&= 3186\; 65857\; 83403\; 11511\; 67461\; \text {(24 digits)} \\ &=399165290221\cdot 798330580441, \end{split}\end{equation*} which was found by the author in an earlier paper. We give reasons to support the conjecture. The main idea of our method for finding those 21978 21978 C 3 C_3 -spsp ( 2 ) (2) ’s is that we loop on candidates of signatures and kernels with heights bounded, subject those candidates N = q 1 q 2 q 3 N=q_1q_2q_3 of C 3 C_3 -spsp ( 2 ) (2) ’s and their prime factors q 1 , q 2 , q 3 q_1,q_2,q_3 to Miller’s tests, and obtain the desired numbers. At last we speed our algorithm for finding larger C 3 C_3 -spsp’s, say up to 10 50 10^{50} , with a given signature to more prime bases. Comparisons of effectiveness with Arnault’s and our previous methods for finding C 3 C_3 -strong pseudoprimes to the first several prime bases are given.

“The problem of distinguishing prime numbers from composite numbers, and of resolving the latter into their prime factors is known to be one of the most important and useful in arithmetic. It has engaged the industry and wisdom of ancient and modern geometers to such an extent that it would be superfluous to discuss the problem at length. Nevertheless we must confess that all methods that have been proposed thus far are either restricted to very special cases or are so laborious and difficult that even for numbers that do not exceed the limits of tables constructed by estimable men, they try the patience of even the practiced calculator. And these methods do not apply at all to larger numbers ... It frequently happens that the trained calculator will be sufficiently rewarded by reducing large numbers to their factors so that it will compensate for the time spent. Further, the dignity of the science itself seems to require that every possible means be explored for the solution of a problem so elegant and so celebrated ... It is in the nature of the problem that any method will become more complicated as the numbers get larger. Nevertheless, in the following methods the difficulties increase rather slowly ... The techniques that were previously known would require intolerable labor even for the most indefatigable calculator.” —from article 329 of Disquisitiones Arithmeticae (1801) by C. F. Gauss There are few better known or more easily understood problems in pure mathematics than the question of rapidly determining whether a given integer is prime. As we read above, the young Gauss in his first book Disquisitiones Arithmeticae regarded this as a problem that needs to be explored for “the dignity” of our subject. However it was not until the modern era, when questions about primality testing and factoring became a central part of applied mathematics, that there was a large group of researchers endeavoring to solve these questions. As we shall see, most of the key ideas in recent work can be traced back to Gauss, Fermat and other mathematicians from times long gone by, and yet there is also a modern spin: With the growth of computer science and a need to understand the true difficulty of a computation, Gauss’s vague assessment “intolerable labor” was only recently Received by the editors January 27, 2004, and, in revised form, August 19, 2004. 2000 Mathematics Subject Classification. Primary 11A51, 11Y11; Secondary 11A07, 11A41, 11B50, 11N25, 11T06. L’auteur est partiellement soutenu par une bourse du Conseil de recherches en sciences naturelles et en genie du Canada. Because of their use in the data encryption employed by public key cryptographic schemes

Let σ ( n ) \sigma (n) denote the sum of the positive divisors of n n . We say that n n is perfect if σ ( n ) = 2 n \sigma (n) = 2 n . Currently there are no known odd perfect numbers. It is known that if an odd perfect number exists, then it must be of the form N = p α ∏ j = 1 k q j 2 β j N = p^\alpha \prod _{j=1}^k q_j^{2 \beta _j} , where p , q 1 , … , q k p, q_1, \ldots , q_k are distinct primes and p ≡ α ≡ 1 ( mod 4 ) p \equiv \alpha \equiv 1 \pmod {4} . Define the total number of prime factors of N N as Ω ( N ) := α + 2 ∑ j = 1 k β j \Omega (N) := \alpha + 2 \sum _{j=1}^k \beta _j . Sayers showed that Ω ( N ) ≥ 29 \Omega (N) \geq 29 . This was later extended by Iannucci and Sorli to show that Ω ( N ) ≥ 37 \Omega (N) \geq 37 . This paper extends these results to show that Ω ( N ) ≥ 47 \Omega (N) \geq 47 .

This is the published version, also available here: http://dx.doi.org/10.1090/S0002-9939-03-07282-4. First published in Proc. Amer. Math. Soc. in 2004, published by the American Mathematical Society.

Ψ(x,y) denotes the number of positive integers y. Hildebrand and Tenenbaum provided a good approximation of Ψ(x,y). However, their method requires the solution a = α(x,y) to the equation Σ p≤y log p/(p α -1) = log x, and therefore it needs a large amount of time for the numerical solution of the above equation for large y. Hildebrand also showed 1-ξ u /log y approximates α for 1 0. We show E(m) approximates ξ u , and i-E(m)/log y also approximates α, where m = ?(log u+log log y)/log log u? + 1. Using these approximations, we give a simple method which approximates Ψ(x,y) within a factor 1 + O(1/u + 1/log y) in the range (log log x) 5/3+ ∈ < logy < (log x)/e, where e is any positive constant.

Define ψm to be the smallest strong pseudoprime to all the first m prime bases. If we know the exact value of ψm, we will have, for integers n > ψm, a deterministic efficient primality testing algorithm which is easy to implement. Thanks to Pomerance et al. and Jaeschke, the ψm are known for 1 ≤ m ≤ 8. Upper bounds for ψg, ψ10 and ψ11 were first given by Jaeschke, and those for ψ10 and ψ11 were then sharpened by the first author in his previous paper (Math. Comp. 70 (2001), 863-872).In this paper, we first follow the first author's previous work to use biquadratic residue characters and cubic residue characters as main tools to tabulate all strong pseudoprimes (spsp's) n > 1024 to the first five or six prime bases, which have the form n = pq with p,q odd primes and q - 1 = k(p-1), k = 4/3, 5/2, 3/2, 6; then we tabulate all Carmichael numbers > 1020, to the first six prime bases up to 13, which have the form n = q1q2q3 with each prime factor qi ≡ 3 mod 4. There are in total 36 such Carmichael numbers, 12 numbers of which are also spsp's to base 17; 5 numbers are spsp's to bases 17 and 19; one number is an spsp to the first 11 prime bases up to 31. As a result the upper bounds for ψ9, ψ10 and ψ11 are lowered from 20- and 22-decimal-digit numbers to a 19-decimal-digit number: ψ9 ≤ ψ10 ≤ ψ11 ≤ Q11 = 3825 12305 65464 13051 (19 digits) = 149491 ċ 747451 ċ 34233211. We conjecture that ψ9 = ψ10 = ψ11 = 3825 12305 65464 13051, and give reasons to support this conjecture. The main idea for finding these Carmichael numbers is that we loop on the largest prime factor q3 and propose necessary conditions on n to be a strong pseudoprime to the first 5 prime bases. Comparisons of effectiveness with Arnault's, Bleichenbacher's, Jaeschke's, and Pinch's methods for finding (Carmichael) numbers with three prime factors, which are strong pseudoprimes to the first several prime bases, are given.

We say n ∈ N is perfect if σ(n) = 2n, where σ(n) denotes the sum of the positive divisors of n. No odd perfect numbers are known, but it is well known that if such a number exists, it must have prime factorization of the form n = pα Φj=1k qj2βj, where p,q1,..., qk are distinct primes and p ≡ α ≡ 1 (mod 4). We prove that if βj ≡ 1 (mod 3) or βj ≡ 2 (mod 5) for all j, 1 ≤ j ≤ k, then 3|n. We also prove as our main result that Ω(n) ≥ 37, where Ω(n) = α + 2 Σj=1k βj. This improves a result of Sayers (Ω(n) ≥ 29) given in 1986.

We present efficient algorithms for solving Legendre equations over Q (equivalently, for finding rational points on rational conics) and parametrizing all solutions. Unlike existing algorithms, no integer factorization is required, provided that the prime factors of the discriminant are known.

We prove that for integers a > b > c > 0 a>b>c>0 , the greatest prime factor of ( a b + 1 ) ( a c + 1 ) (ab+1)(ac+1) tends to infinity with a a . In particular, this settles a conjecture raised by Györy, Sarkozy and Stewart, predicting the same conclusion for the product ( a b + 1 ) ( a c + 1 ) ( b c + 1 ) (ab+1)(ac+1)(bc+1) .

We derive a conditional formula for the natural density E(q) of prime numbers p having its least prime primitive root equal to q, and compare theoretical results with the numerical evidence.

Let A A be a Noetherian Cohen-Macaulay domain, b b , c 1 c_1 , … \dots , c g c_g an A A -sequence, J J = ( b , c 1 , … , c g ) A (b,c_1,\dots ,c_g)A , and B B = A [ J / b ] A[J/b] . Then B B is Cohen-Macaulay, there is a natural one-to-one correspondence between the sets Ass B ⁡ ( B / b B ) \operatorname {Ass}_B(B/bB) and Ass A ⁡ ( A / J ) \operatorname {Ass}_A(A/J) , and each q q ∈ \in Ass A ⁡ ( A / J ) \operatorname {Ass}_A(A/J) has height g + 1 g+1 . If B B does not have unique factorization, then some height-one prime ideals P P of B B are not principal. These primes are identified in terms of J J and P ∩ A P \cap A , and we consider the question of how far from principal they can be. If A A is integrally closed, necessary and sufficient conditions are given for B B to be integrally closed, and sufficient conditions are given for B B to be a UFD or a Krull domain whose class group is torsion, finite, or finite cyclic. It is shown that if P P is a height-one prime ideal of B B , then P ∩ A P \cap A also has height one if and only if b b ∉ \notin P P and thus P ∩ A P \cap A has height one for all but finitely many of the height-one primes P P of B B . If A A has unique factorization, a description is given of whether or not such a prime P P is a principal prime ideal, or has a principal primary ideal, in terms of properties of P ∩ A P \cap A . A similar description is also given for the height-one prime ideals P P of B B with P ∩ A P \cap A of height greater than one, if the prime factors of b b satisfy a mild condition. If A A is a UFD and b b is a power of a prime element, then B B is a Krull domain with torsion class group if and only if J J is primary and integrally closed, and if this holds, then B B has finite cyclic class group. Also, if J J is not primary, then for each height-one prime ideal p p contained in at least one, but not all, prime divisors of J J , it holds that the height-one prime p A [ 1 / b ] ∩ B pA[1/b] \cap B has no principal primary ideals. This applies in particular to the Rees ring R {\mathbf R} = = A [ 1 / t , t J ] A[1/t, tJ] . As an application of these results, it is shown how to construct for any finitely generated abelian group G G , a monoidal transform B B = A [ J / b ] A[J/b] such that A A is a UFD, B B is Cohen-Macaulay and integrally closed, and G G ≅ \cong Cl ⁡ ( B ) \operatorname {Cl}(B) , the divisor class group of B B .

Erdos conjectured that there are x1-o(1) Carmichael numbers up to x, whereas Shanks was skeptical as to whether one might even find an x up to which there are more than √x Carmichael numbers. Alford, Granville and Pomerance showed that there are more than x2/7 Carmichael numbers up to x, and gave arguments which even convinced Shanks (in person-to-person discussions) that Erdos must be correct. Nonetheless, Shanks's skepticism stemmed from an appropriate analysis of the data available to him (and his reasoning is still borne out by Pinch's extended new data), and so we herein derive conjectures that are consistent with Shanks's observations, while fitting in with the viewpoint of Erdos and the results of Alford, Granville and Pomerance.

We describe a successful search for a sequence of fifteen consecutive integers, each the product of exactly four prime factors. Fifteen is best possible.

Let c ≥ 2 be an even integer, (3, c) = 1. The resultant Wc of the polynomials tc - 1 and (1 + t)c - 1 is known as Wendt's determinant of order c. We prove that among the prime divisors q of Wc only those which divide 2c - 1 or Lc/2 can be larger than θc/4, where θ = 2.2487338 and Ln is the nth Lucas number, except when c = 20 and q = 61. Using this estimate we derive criteria for the nonsolvability of Fermat's congruence.

In this paper we show that the set of positive odd integers k k such that k 2 n + 1 k2^{n} +1 has at least three distinct prime factors for all positive integers n n has positive lower asymptotic density.

If a nontrivial nilpotent group N acts faithfully and coprimely on a group H, it is shown that some element of H has a small centralizer in N and hence lies in a large orbit. Specifically, there exists x G H such that ICN(X)I < (INI/p)l/P, where p is the smallest prime divisor of INi.

It is proved here that every odd perfect number is divisible by a prime greater than 10 6 10^{6} .

A search for prime factors of the generalized Fermat numbers F n ( a , b ) = a 2 n + b 2 n F_n(a,b)=a^{2^n}+b^{2^n} has been carried out for all pairs ( a , b ) (a,b) with a , b ≤ 12 a,b\leq 12 and GCD ( a , b ) = 1 (a,b)=1 . The search limit k k on the factors, which all have the form p = k ⋅ 2 m + 1 p=k\cdot 2^m+1 , was k = 10 9 k=10^9 for m ≤ 100 m\leq 100 and k = 3 ⋅ 10 6 k=3\cdot 10^6 for 101 ≤ m ≤ 1000 101\leq m\leq 1000 . Many larger primes of this form have also been tried as factors of F n ( a , b ) F_n(a,b) . Several thousand new factors were found, which are given in our tables.—For the smaller of the numbers, i.e. for n ≤ 15 n\leq 15 , or, if a , b ≤ 8 a,b\leq 8 , for n ≤ 16 n\leq 16 , the cofactors, after removal of the factors found, were subjected to primality tests, and if composite with n ≤ 11 n\leq 11 , searched for larger factors by using the ECM, and in some cases the MPQS, PPMPQS, or SNFS. As a result all numbers with n ≤ 7 n\leq 7 are now completely factored.

For a positive integer k k , the Erdös-Selfridge function is the least integer g ( k ) > k + 1 g(k) > k+1 such that all prime factors of ( g ( k ) k ) \binom {g(k)}{k} exceed k k . This paper describes a rapid method of tabulating g ( k ) g(k) using VLSI based sieving hardware. We investigate the number of admissible residues for each modulus in the underlying sieving problem and relate this number to the size of g ( k ) g(k) . A table of values of g ( k ) g(k) for 135 ≤ k ≤ 200 135 \leq k \leq 200 is provided.

Let E / Q E/ \mathbb {Q} be an elliptic curve with discriminant Δ \Delta , and let P ∈ E ( Q ) P\in E( \mathbb {Q}) . The standard method for computing the canonical height h ^ ( P ) \hat h(P) is as a sum of local heights h ^ ( P ) = λ ^ ∞ ( P ) + ∑ p λ ^ p ( P ) \hat h (P)= \hat \lambda _{\infty }(P)+\sum _{p} \hat \lambda _{p}(P) . There are well-known series for computing the archimedean height λ ^ ∞ ( P ) \hat \lambda _{\infty }(P) , and the non-archimedean heights λ ^ p ( P ) \hat \lambda _{p}(P) are easily computed as soon as all prime factors of Δ \Delta have been determined. However, for curves with large coefficients it may be difficult or impossible to factor Δ \Delta . In this note we give a method for computing the non-archimedean contribution to h ^ ( P ) \hat h (P) which is quite practical and requires little or no factorization. We also give some numerical examples illustrating the algorithm.

We describe an algorithm for constructing Carmichael numbers N N with a large number of prime factors p 1 , p 2 , … , p k p_{1}, p_{2}, \dots , p_{k} . This algorithm starts with a given number Λ = lcm ⁡ ( p 1 − 1 , p 2 − 1 , … , p k − 1 ) \Lambda =\operatorname {lcm} (p_{1}-1, p_{2}-1, \dots ,p_{k}-1) , representing the value of the Carmichael function λ ( N ) \lambda (N) . We found Carmichael numbers with up to 1101518 1101518 factors.