All the data you need.

Tag: Number Theory

Factoring b^n – 1
Suppose you want to factor a number of the form bn – 1. There is a theorem that says that if m divides n then bm – 1 divides bn – 1. Let’s use this theorem to try to factor J = 22023 – 1, a 609-digit number. Factoring such …
Special primality proofs
I’ve written lately about two general ways to prove that a number is prime: Pratt certificates for moderately-large primes and elliptic curve certificates for very large primes. If you can say more about the prime you wish to certify, there may be special forms of certificates that are more efficient. …
Elliptic curve primality certificates
I’ve written recently about a simple kind of primality certificates, Pratt certificates. These certificates are easy to understand, and easy to verify, but they’re expensive to produce. In order to produce a Pratt certificate that n is a prime you have to factor n-1, and that can take a long …
Primes with two non-zero bits
Suppose a number n written in binary has two 1s and all the rest of its bits are zeros. If n is prime, then the 1s must be the first and last bits of n. The first bit is 1 because the first bit of every positive integer is 1. …
Certified sonnet primes
Last week I wrote about primailty certificates. These certificates offer a way to verify that a number is prime using less computation than was used to discover than the number was prime. This post gives a couple more examples of primality certificates using sonnet primes. As described here, These are …
Pratt Primality Certificates
The previous post implicitly asserted that J = 8675309 is a prime number. Suppose you wanted proof that this number is prime. You could get some evidence that J is probably prime by demonstrating that 2J-1 = 1 mod J. You could do this in Python by running the following …
Quadratic reciprocity algorithm
The quadratic reciprocity theorem addresses the question of whether a number is a square modulo a prime. For an odd prime p, the Legendre symbol is defined to be 0 if a is a multiple of p, 1 if a is a (non-zero) square mod p, and -1 otherwise. It …
Pascal’s triangle mod row number
Almost all binomial coefficients are divisible by their row number. This is a theorem from [1]. What does it mean? If you iterate through Pascal’s triangle, left-to-right and top-to-bottom, noting which entries C(m, k) are divisible by m, the proportion approaches 1 in the limit. The author proves that the …
Repunits: primes and passwords
A repunit is a number whose base 10 representation consists entirely of 1s. The number consisting of n 1s is denoted Rn. Repunit primes A repunit prime is, unsurprisingly, a repunit number which is prime. The most obvious example is R2 = 11. Until recently the repunit numbers confirmed to …
Average digit sum
Suppose you write down a number and take the sum of its digits. In what base will this sum be the smallest on average? Let’s do a couple examples comparing base 10 and base 2. The number 2022 in base 10 has digit sum 6, but its binary equivalent 11111100110 …
Cicadas and Chicken Nuggets
Yesterday I wrote about the Chicken McNugget problem: if Chicken McNuggets are sold in boxes of 6, 9, and 20, what’s the least number of nuggets you cannot buy? That post showed that the solution was 43. The technical name for these kinds of problems is numerical monoids. The method …
Sum of squares mod n uniformly distributed
Let s be an integer equal to at least 5 and let n be a positive integer. Look at all tuples of s integers, each integer being between 0 and n-1 inclusive, and look at the sum of their squares mod n. About 1/n will fall into each possible value. …
Conway’s factoring trick
The numbers 152 through 156 have a lot of small prime factors. I’ll be more explicit about that shortly, but take my word for it for now. John Conway [1] took this simple observation and turned it into a technique for mentally factoring integers. Conway’s factoring method To look for …
Phi Phi
I was reading something this afternoon and ran across φ(φ(m)) and thought that was unusual. I often run across φ(m), the number of positive integers less than m and relative prime to m, but don’t often see Euler’s phi function iterated. Application of φ∘φ This section will give an example …
Infinite periodic table
All the chemical elements discovered or created so far follow a regular pattern in how their electrons are arranged: the nth shell contains up to 2n – 1 suborbitals that each contain up to two electrons. For a given atomic number, you can determine how its electrons are distributed into …
Looking for the next prime
Suppose you start with some large number x and want to find a prime number at least as big as x. First you test whether x is prime. Then you test whether x + 1 is prime. Then you test whether x + 2 is prime, and so on until …
Beatty’s theorem
Here’s a surprising theorem [1]. (Beatty’s theorem) Let a and b be any pair of irrational numbers greater than 1 with 1/a + 1/b = 1. Then the sequences { ⌊na⌋ } and { ⌊nb⌋ } contain every positive integer without repetition. Illustration Here’s a little Python code to play …
Turning the Golay problem sideways
I’ve written a couple posts about the Golay problem recently, first here then here. The problem is to find all values of N and n such that is a power of 2, say 2p. Most solutions apparently fall into three categories: n = 0 or n = N, N is …