Freshman’s dream

The Freshman's dream" is the statement

(x+ y)^p = x^p + y^p

It's not true in general, but itis true modp if p is a prime. It's a cute result, but it's also useful in applications, such as finite field computations in cryptography.

Here's a demonstration of the Freshman's dream in Python.

>>> p = 5>>> [((x + y)**p - x**p - y**p) % p for x in range(p) for y in range(p)][0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

Here's an example using a prime too large for verify the results by looking at the output.

>>> import numpy as np>>> p = 103>>> v = [((x + y)**p - x**p - y**p) % p for x in range(p) for y in range(p)]>>> np.all( np.array(v) == 0 )True

You can use the same code to show that the Freshman's dream is not true in general if p is not a prime, and it's not true in general if p is a prime but the exponent is less than p.

The post Freshman's dream first appeared on John D. Cook.