In 2013, John Conway and Alex Ryba published a brief note [1] on how to convert identities involving sine and cosine into identities involving Fibonacci and Lucas numbers.

Fibonacci and Lucas

The Fibonacci numbers F_n are defined by F₀ = 0, F₁ = 1, and

F_n+2 = F_n + F_n+1

for n > 1. Similarly, Lucas numbers L_n are defined by the same recurrence relation

L_n+2 = L_n + L_n+1

but starting with L₀ = 2 and L₁ = 1.

The recipe

The recipe for turning trigonometric identities into Fibonacci and Lucas number identities is as follws.

1. Arguments become subscripts.
2. Replace sines by ½ iⁿ F_n.
3. Replace cosines by ½ iⁿ L_n.
4. Insert a factor of (−5)^k in front of every term that contains 2k or 2k + 1 sine terms.

The first step is admittedly unclear. It’s unclear in [1] as well. If sine or cosine takes an argument of

pα + qβ

then this becomes the subscript

pa + qb

where the Latin letters are integers and the Greek letters are angles.

There’s no proof in [1] why the recipe should work, but an earlier paper [2] gives more details.

Examples

Double angle

For a simple example, let’s start with the double angle identity

sin 2θ = 2 sin θ cos θ.

This becomes

½ i²ⁿ F_2n = 2 (½ iⁿ F_n)(½ iⁿ L_n)

which simplifies to

F_2n = F_n L_n.

Sum angle

For a little more involved example, let’s look at the sum identity

cos(θ + φ) = cos θ cos φ − sin θ sin φ.

This becomes

½ i^{a + b} L_{a + b} = ½ i^a L_a ½ i^b L_b −(−5) ½ i^a F_a ½ i^b F_b

which simplifies to

2L_{a + b} = L_a L_b  + 5 F_a F_b.

Triple angle

In the previous examples the powers of i in the recipe above cancelled out. This example will show that they are necessary.

We start with the triple angle identity

sin 3θ = 3 sin θ − 4 sin³ θ.

This becomes

½ i³ⁿ F_3n = 3 (½) iⁿ F_n − 4(−5)(½ iⁿ F_n)³

which simplifies to

F_3n = 3 (−1)ⁿ F_n + 5 (F_n)³.

Demonstration

The following Python code demonstrates that the Fibonacci / Lucas identities above are correct.

def F(n):
    if n == 0: return 0
    if n == 1: return 1
    return F(n-1) + F(n-2)

def L(n):
    if n == 0: return 2
    if n == 1: return 1
    return L(n-1) + L(n-2)

for n in range(10):
    assert(F(2*n) == F(n) * L(n))

for n in range(10):
    for m in range(10):
        assert(2*L(m + n) == L(m)*L(n) + 5*F(m)*F(n))

for n in range(10):
    assert(F(3*n) == 3*(-1)**n * F(n) + 5*F(n)**3)

Related posts

• Convert trig identities to hyperbolic identities
• Inverse Fibonacci numbers
• Lucas numbers and Lucas pseudoprimes
• Trig mnemonic diagrams

[1] John Conway and Alex Ryba. Fibonometry. The Mathematical Gazette, November 2013, pp. 494–495

[2] Barry Lewis, Trigonometry and Fibonacci Numbers, The Mathematical Gazette, July 2007, pp. 216–226

This morning I took an old blog post and turned it into an X thread. I think the thread is easier to read. More expository and less rigorous.

The post and thread look at generalizations of the fact that every integer and its fifth power end in the same digit. The conclusion is that n and n^k end in the same digit base b if b is square-free and k = φ(b) + 1. So, for example, 10 is square-free (i.e. not divisible by a non-trivial square) and φ(10) + 1 = 5.

Benjamin Clark replied suggesting looking at λ(b) + 1 in addition to φ(n) + 1.

Euler and Carmichael

To back up a bit, φ(n) is Euler’s totient function, the number of positive integers less than and relatively prime to n. Robert Carmichael’s totient function λ(n) is a closely related function, one that replaced Euler’s function in implementations of RSA encryption—more specifically in RSA decryption—something I wrote about earlier this week.

Euler’s generalization of Fermat’s little theorem says if a is relatively prime to m, then

a^φ(n) = 1 (mod n).

Carmichael’s totient λ(n) is the smallest number such that

a^λ(n) = 1 (mod n)

when a is relatively prime to n.

Sometimes φ(n) = λ(n), namely for n = 1, 2, 4, and every odd prime power. Otherwise λ(n) is a proper divisor of φ(n).

Carmichael’s conjecture

Carmichael conjectured that for every n there is at least one other integer m ≠ n such that φ(m) = φ(n). He proved that this is true at least for n less than 10³⁷. The conjecture is now known to be true for n less than 10¹⁰¹⁰.

Fermat numbers

The nth Fermat number is defined by

Pierre Fermat conjectured that the F(n) were prime for all n, and they are for n = 0, 1, 2, 3, and 4, but Leonard Euler factored F(5), showing that it is not prime.

Tangent numbers

The nth tangent number is defined by the Taylor series for tangent:

Another way to put it is that the exponential generating function for T(n) is tan(z).

Fermat primes and tangent numbers

Here’s a remarkable connection between Fermat numbers and tangent numbers, discovered by Richard McIntosh as an undergraduate [1]:

F(n) is prime if and only if F(n) does not divide T(F(n) − 2).

That is, the nth Fermat number is prime if and only if it does not divide the (F(n) − 2)th tangent number.

We could duplicate Euler’s assessment that F(5) is not prime by showing that 4294967297 does not divide the 4294967295th tangent number. That doesn’t sound very practical, but it’s interesting.

Update: To see just how impractical the result in this post would be for testing whether a Fermat number is prime, I found an asymptotic estimate of tangent numbers on OEIS,  and estimated that the 4294967295th tangent number has about 80 billion digits.

[1] Richard McIntosh. A Necessary and Sufficient Condition for the Primality of Fermat Numbers. The American Mathematical Monthly, Vol. 90, No. 2 (Feb., 1983), pp. 98–99

A rational triangle is a triangle whose sides have rational length and whose area is rational. Can any two rational numbers be sizes of a rational triangle? Surprisingly no. You can always find a third side of rational length, but it might not be possible to do so while keeping the area rational.

The following theorem comes from [1].

Let q be a prime number not congruent to 1 or −1 mod 8. And let ω be an odd integer such that no prime factor of q^2ω − 1 is congruent to 1 mod 4. Then a = q^ω + 1 and b = q^ω − 1 are not the sides of any rational triangle.

To make the theorem explicitly clear, here’s a Python implementation.

from sympy import isprime, primefactors

def test(q, omega):
    if not isprime(q):
        return False
    if q % 8 == 1 or q % 8 == 7:
        return False
    if omega % 2 == 0:
        return False
    factors = primefactors(q**(2*omega) - 1)
    for f in factors:
        if f % 4 == 1:
            return False
    return True

We can see that q = 2 and ω = 1 passes the test, so there is no rational triangle with sides a = 2¹ + 1 = 3 and b = 2¹ − 1 = 1.

You could use the code above to search for (a, b) pairs systematically.

from sympy import primerange

for q in primerange(20):
    for omega in range(1, 20, 2):
        if test(q, omega):
            a, b = q**omega + 1, q**omega - 1
            print(a, b)

This outputs the following:

3 1
9 7
33 31
129 127
8193 8191
32769 32767
131073 131071
524289 524287
4 2
6 4
126 124
14 12

Note that one of the outputs is (4, 2). Since multiplying the sides of a rational triangle by a rational number gives another rational triangle, there cannot be a rational triangle in which one side is twice as long as another.

As the author in [1] points out, “There are undoubtedly many pairs not covered by [the theorem cited above]. It would be of interest to characterize all pairs.” The paper was published in 1976. Maybe there has been additional work since then.

Related posts

• Rational right triangles
• The congruent number problem
• Do perimeter and area determine a triangle?
• Approximation with Pythagorean triangles

[1] N. J. Fine. On Rational Triangles. The American Mathematical Monthly. Vol. 83. No. 7, pp. 517–521.

I recently ran across an article by Katherine Stange [1] on Lehmer’s factoring stencils [2]. These stencils were the basis of an effective method for factoring moderately large numbers before the advent of electronic computers.

This post will describe the stencils and simulate their use with a Python script.

Misconceptions

When I started reading [1] I had three misconceptions that slowed down my understanding of the article. I’ll address these first in case any of you come to this article with the same unhelpful expectations.

First, when I saw something about using stencils for factoring I thought they would be something like a Sieve of Eratosthenes, stencils with multiples of 2, 3, 5, etc. cut out. That is not what’s going on; Lehmer’s method is more sophisticated than that.

Second, related to the first, I thought that the factoring method would involve placing stencils on top of a large grid of numbers that included the number you wanted to factor. That is also not the case. The stencils can be used to factor nine-digit numbers, and a sheet of over a billion numbers would not be practical.

Third, I thought there might be some geometric significance to the position of the holes in the circular stencils. There isn’t. The stencils were circular for convenience.

How the stencils worked

Lehmer made a set of 295 stencils. Katherine Stange has put a set of SVG files for such stencils on her Github repo. The image below is the stencil corresponding to the number 42.

I want focus on how the stencils work, not why they work.

To factor a number N, you would first find a handful of numbers X₁, X₂, X₃, … X_k, related to N, numbers that are fairly easy to compute by hand. Then you would stack the stencils corresponding to the X_i and hold the stack up to the light.

If y is a quadratic residue mod N, then y is a quadratic residue mod each of the prime factors of N. Each stencil cuts the number of potential prime factors by about a half.

Once you found a probable prime factor, you would test it by long division, and then you know with certainty whether the number is a factor.

What is each stencil?

So what are these X_i and what are the holes in them?

The X_i are quadratic residues mod N, i.e. numbers such that

X_i = x² mod N

has a solution. This would have required some hand calculation, but not nearly as much calculation as trying to factor N unaided. A couple algorithms for finding quadratic residues are described in this video and in this PDF by Katherine Stange.

NB: The hard part isn’t finding quadratic residues mod N; you could do that by squaring random integers mod N. The hard part is finding quadratic residues that correspond to your set of available stencils.

The holes in the stencil correspond to the prime numbers up to 48593. Disk X has a hole for prime p if X is a quadratic residue mod X. If X is a quadratic residue mod p and mod N, there’s a 50-50 chance p divides N.

The number 48593 is the 4999th prime, so there are locations on each disk corresponding to 4999 primes. Lehmer arranged these locations in a spiral, but they could have been laid out in a grid or any other pattern.

Python simulation

See the Github repo referenced above for Python code to make the SVG files for the physical stencils. The Python code below simulates the operation of the stencils, not their geometry. I wrote the code to be illustrative, not to be practical efficient code for factoring integers.

First, here’s code to make our stencils. Here a 1 corresponds to a hole.

from sympy import primerange, legendre_symbol
from numpy import array

primes = array([p for p in primerange(3, 48594)])

def stencil(x):
    # stencil has a 1 in position k if x is a quadratic residue
    # modulo the kth odd prime and a 0 otherwise
    return array([1 if legendre_symbol(x, p) >= 0 else 0 for p in primes])

Next we pick an N and a few small quadratic residues mod N.

N = 19972009 
x = [2, 61, 79, 185, 238, 255, 313, 421, 491]

Multiplying the stencils together produces a 1 where every stencil has a hole.

mask = stencil(x[0])
for i in range(1, len(x)):
    mask *= stencil(x[i])
ps = mask*primes
print(ps[ps != 0])

This prints the following:

[ 97 103 1367 1999 15241 28351 35353 36847 44953]

We then test whether each of these primes is a factor of N, and in fact

19972009 = 97 × 103 × 1999.

Each stencil has 4999 primes, and if each of the 9 stencils eliminates about half the potential prime factors, we’d expect around 4999/2⁹ ≈ 10 candidate primes, which is very close to what we got.

Related posts

• Conway’s mental factoring method
• Factored random numbers
• Numbers don’t typically have many prime factors

[1] The Ingenious Physical Factoring Devices of D. N. Lehmer. Math Horizons. Volume 30 Issue 2. November 2022.

[2] D. N. Lehmer and his son D. H. Lehmer were both number theorists. I’ve referred to the later several times on the blog, most recently here. I also cited Katherine Stange a couple weeks ago.

The following prime number looks like a black-and-white image of an American flag.

The number mostly consists of the digits 1, 3, and 8, but there are a few 9’s. The following image colors the 8’s blue, the 3’s red, and the 1’s white. The background is gray so you can see the 1s.

I found this in [1]. The article includes a link to a text version of the number, but the link is broken, so I had to convert the image to text.

Unfortunately tesseract did a poor job, and so did Grok, so I ended up more or less doing the conversion by hand. I made a text version and posted it here.

See the next post for a calculation showing that the number is indeed prime.

[1] The United States of America Prime. Vadim Ponomarenko. Math Horizons, Vol. 28, No. 4 (April 2021)