Tag Archives: test

Modular exponentiation

Posted on August 13, 2018 by Brent

In my previous post I explained the Fermat primality test: Input: Repeat times: Randomly choose . If , stop and output COMPOSITE. Output PROBABLY PRIME. In future posts I’ll discuss how well this works, things to worry about, and so … Continue reading →

Posted in computation, number theory | Tagged exponentiation, modular, primality, test | 2 Comments

The Fermat primality test

Posted on August 3, 2018 by Brent

After several long tangents writing about orthogons and the chromatic number of the plane, I’m finally getting back to writing about primality testing. All along in this series, my ultimate goal has been to present some general primality testing algorithms … Continue reading →

Posted in computation, number theory, primes | Tagged Fermat, primality, test | 5 Comments

Golden numbers are Fibonacci

Posted on March 19, 2016 by Brent

This post is fourth in a series, proving the curious fact that is a Fibonacci number if and only if one (or both) of or is a perfect square; we call numbers of this form golden numbers. Last time, I … Continue reading →

Posted in arithmetic, computation, famous numbers, fibonacci, proof | Tagged Cassini, fibonacci, formula, lucas, square, test | 2 Comments

Fibonacci numbers are golden

Posted on February 28, 2016 by Brent

Recall that a “golden number” (this is not standard terminology) is a number such that one (or both) of or is a perfect square. In this post, I’ll explain Gessel’s proof that every Fibonacci number is golden. First, we need … Continue reading →

Posted in arithmetic, computation, famous numbers, fibonacci, proof | Tagged Cassini, fibonacci, formula, lucas, square, test | 1 Comment

Testing Fibonacci numbers: the proofs

Posted on February 27, 2016 by Brent

In my last post I stated this surprising theorem: is a Fibonacci number if and only if one of is a perfect square. If one of is a perfect square, then let’s say that is a “golden number” (a nod, … Continue reading →

Posted in arithmetic, computation, famous numbers, fibonacci, proof | Tagged fibonacci, formula, square, test | 1 Comment

Testing Fibonacci numbers

Posted on February 26, 2016 by Brent

From a recent post on Brian Hayes’ blog, bit-player, I learned the following curious fact: is a Fibonacci number if and only if either or is a perfect square. Recall that the Fibonacci numbers begin where each number is the … Continue reading →

Posted in arithmetic, computation, famous numbers, fibonacci | Tagged fibonacci, formula, square, test | 8 Comments

MaBloWriMo 23: contradiction!

Posted on November 24, 2015 by Brent

So, where are we? We assumed that is divisible by , but is not prime. We picked a divisor of and used it to define a group , and yesterday we showed that has order in . Today we’ll use … Continue reading →

Posted in algebra, group theory, modular arithmetic, number theory, proof | Tagged contradiction, groups, lehmer, lucas, MaBloWriMo, Mersenne, omega, order, prime, proof, test, X | 5 Comments

MaBloWriMo 22: the order of omega, part II

Posted on November 23, 2015 by Brent

Yesterday, from the assumption that is divisible by , we deduced the equations and which hold in the group . So what do these tell us about the order of ? Well, first of all, the second equation tells us … Continue reading →

Posted in algebra, group theory, modular arithmetic, number theory, proof | Tagged groups, lehmer, lucas, MaBloWriMo, Mersenne, omega, order, prime, proof, test, X | 1 Comment

MaBloWriMo 21: the order of omega, part I

Posted on November 22, 2015 by Brent

Now we’re going to figure out the order of in the group . Remember that we started by assuming that passed the Lucas-Lehmer test, that is, that is divisible by . Remember that we also showed for all . In … Continue reading →

Posted in algebra, group theory, modular arithmetic, number theory, proof | Tagged groups, lehmer, lucas, MaBloWriMo, Mersenne, omega, order, prime, proof, test, X | 2 Comments

MaBloWriMo 16: Recap and outline

Posted on November 17, 2015 by Brent

We have now established all the facts we will need about groups, and have incidentally just passed the halfway point of MaBloWriMo. This feels like a good time to take a step back and outline what we’ve done so far … Continue reading →

Posted in algebra, arithmetic, computation, famous numbers, group theory, iteration, modular arithmetic, number theory, primes | Tagged groups, lehmer, lucas, MaBloWriMo, Mersenne, omega, prime, proof, summary, test | 2 Comments