Challenge

Challenge Numbers

2024 and Differences of Squares — Solution

The new year 2024 is a difference of squares, $2024 = 45^2 - 1^2$ , which got me thinking about a fun little number theory problem:

Is there a largest number that can not be expressed as the difference of squares? If so, find it. If not, prove no such number exists. Good luck, and happy new year!

As promised, here’s my solution.

There are infinitely many numbers that can not be expressed as a difference of squares. In fact, we can completely characterize numbers that can be expressed as a difference of squares and those that can’t. It all starts with factoring.

Differences of squares have a useful structure that can be exposed by factoring:

$a^2 - b^2 = (a + b) \times (a - b)$

We can leverage this structure to answer our question.

Suppose n can be factored as $n = s \times t$ . If n can be expressed as a difference of squares, then we can also write

$n = a^2 - b^2= (a + b) \times (a - b)$

Now set $(a + b) = s$ and $(a - b) = t$ . This gives us the system of equations

$a + b = s$

$a - b = t$

We can solve this system by adding and subtracting the equations. Adding gives us $a = \frac{s+t}{2}$ , and subtracting gives us $b = \frac{s-t}{2}$ . This shows us how to express n as a difference of squares: Just factor n into $s \times t$ , compute $a = \frac{s+t}{2}$ and $b = \frac{s-t}{2}$ , and then $n = (a + b) \times (a - b) = a^2 - b^2$ .

There’s only one thing we have to worry about: a and b must be integers. But as long as s and t have the same parity — that is, s and t are both even or both odd — then the sum and difference of s and t will both be even, and so $\frac{s \pm t}{2}$ will be an integer.

This means that n can be expressed as a difference of squares if and only if we can write $n = s \times t$ where s and t are both odd or both even. This is usually possible, often in multiple ways. But there’s one situation when it isn’t: When n is divisible by 2 exactly once. When this is true, then however you factor n into $s \times t$ , the lone factor of 2 will end up as a part of either s or t, making one of them even and the other odd. Thus, in this case, it’s impossible to factor n so that the two factors have the same parity, and so it’s impossible to express n as a difference of squares.

This gives us a complete answer to our question: A number n is not expressible as a difference of squares if and only if it is divisible by 2 exactly once! In other words, every odd number times 2 is not expressible as a difference of squares, and every other integer is.

As an example, given $n = 105 = 3 \times 5 \times 7$ , we can factor $105 = 7 \times 15$ which gives $a=\frac{15+7}{2}= 11$ and $a=\frac{15-7}{2}=4$ , and sure enough, $105 = 11^2 - 4^2$ . Notice, we could also write $105 = 5 \times 21$ , which gives $a = \frac{21+5}{2}=13$ and $b = \frac{21-5}{2}=8$ , so $105 = 13^2 - 8^2$ .

On the other hand, it isn’t possible to do this at all for 6. There are only two factorizations, $6 = 6 \times 1$ and $6 = 2 \times 3$ , and in both cases the factors have different parity, so the a and b we need won’t be integers.

There’s an interesting resemblance here to Euclid’s Formula for generating Pythagorean triples. There’s also an interesting follow-up question about how many different ways a number can be expressed as a difference of squares. And since the numbers that answer our question are those that are divisible by 2 exactly once, I wonder what properties numbers that are divisible by 3 exactly once have.

Thanks to everyone who contributed on the Mastodon thread! There are some cool ideas there as well, so be sure to check it out.

Related Posts

By MrHonner, 12 months12 months ago

Challenge Numbers

2024 and Differences of Squares

The new year is one of my favorite kinds of numbers: a difference of squares!

$2024 = 46 \times 44 = (45 + 1) \times (45 - 1) = 45^2 - 1^2$

This observation got me thinking about what kinds of numbers can be written as the difference of squares. For example, $3 = 2^2 - 1^2$ , $5 = 3^2 - 2^2$ , and $16 = 4^2 - 0^2$ , but it is impossible to write 6 as the difference of squares of integers.

So here’s a little mathematical puzzle to start the new year: Is there a largest number that can not be expressed as the difference of squares? If so, find it. If not, prove no such number exists. Good luck, and happy new year! I’ll give my answer in a follow-up post.

Related Posts

2024 and Differences of Squares — Solution
The 2017-2018 Conjecture
Happy 2016!

Related Post

By MrHonner, 12 months12 months ago

Challenge Teaching

Who Needs Trig Sub? Part 2

I recently wrote about an ingenious integration performed by two of my students. But that wasn’t the whole story. Here’s the rest.

It begins with this integral.

Usually when challenged to evaluate this integral students will try a few substitutions, fail to find an antiderivative, and realize something new is needed. This sets the stage for trigonometric substitution, which we then use to untangle the algebraic obstacles in the integrand.

But this was an unusual year. Not only did two students surprise me with a purely geometric approach, a third student found another completely different solution I had never seen before. She used integration by parts!

This application of integration by parts leads to the following equation.

Which she simplified to this.

This is the point where I would probably abandon integration by parts, because it doesn’t look the situation has improved. But my student did something incredibly inspired. She rewrote the integral

like this

And this is definitely an improvement. The integral on the right is known: it’s just $arcsin(x)$ . And the other integral is the one we were trying to find in the first place. When this is substituted back into the integration by parts equation you get this

The integral we want to evaluate is now on both sides of the equation, so just collect like terms and solve

Before this year I had never seen any alternate derivation of this formula. This year students produced two completely new ones!

I can understand why students had never attempted this technique before. Integration by parts typically comes after trig substitution in the course, so it wouldn’t usually be an option for them. But this year, because of the way I rearranged the curriculum, integration by parts came first. And I’m thrilled that my student thought to try it. And persevered!

It also made me feel good about my integration by parts lesson. Usually the last problem I present in that lesson is the integral

But this year I almost didn’t. This problem requires repeated integration by parts and quite a bit of perseverance to solve. At the end of a long lesson I considered passing on it, but we pushed through. And it was worth it! Seeing this technique set up my student to find her own ingenious integral. And to teach me something new.

Related Posts

By MrHonner, 4 years4 years ago

Challenge Teaching

sin(x) + cos(x)

Here is a fun little exploration involving a simple sum of trigonometric functions.

Consider f(x) = sin(x) + cos(x), graphed below.

Surprisingly, it appears as though sin(x) + cos(x) is itself a sine function. And while its period is the same as sin(x), its amplitude has changed and it’s been phase-shifted. Figuring out the exact amplitude and phase shift is fun, and it’s also part of a deeper phenomenon to explore.

Consider the function g(x) = a sin(x) + b cos(x). Playing around with the values of a and b is a great way to explore the situation.

On the way to a complete solution, a nice challenge is to find (and characterize) the values of a and b that make the amplitude of g(x) equal to one. It’s also fun to look for values of a and b that yield integer amplitudes: for example, 5sin(x) + 12cos(x) has amplitude 13, and 4sin(x) + 3cos(x) has amplitude 5.

Ultimately, this exploration leads to a really lovely application of angle sum formulas. Recall that

$sin(A + B) = sin(A) cos (B) + sin(B) cos(A)$

If we let A = x, we get

$sin(x + B) = sin(x) cos(B) + sin(B) cos(x)$

With a little rewriting, we have

$sin(x + B) = cos(B) sin(x) + sin(B) cos(x)$

which looks similar to our original function f(x) = sin(x) + cos(x), except for what’s in front of sin(x) and cos(x). We handle that with a clever choice of B.

Let $B = \frac{\pi}{4}$ . Now we have

$sin(x + \frac{\pi}{4}) = cos(\frac{\pi}{4})sin(x) + sin(\frac{\pi}{4})cos(x)$

$sin(x + \frac{\pi}{4}) = \frac{\sqrt{2}}{2} sin(x) + \frac{\sqrt{2}}{2}cos(x)$

And a little algebra gets us

$sin(x) + cos(x) = \sqrt{2}sin(x + \frac{\pi}{4})$

And so sin(x) + cos(x) really is a sine function! Not only does this transformation explain the amplitude and phase shift of sin(x) + cos(x), it generalizes beautifully.

For example, consider 5sin(x) + 12cos(x). We can rewrite this in the following way.

$5sin(x) + 12cos(x) = 13 ( \frac{5}{13} sin(x) + \frac{12}{13} cos(x))$

$5sin(x) + 12cos(x)= 13 ( cos(\beta) sin(x) + sin(\beta) cos(x))$

$5sinx + 12cosx = 13 sin (x + \beta)$

where $\beta = arcsin(\frac{12}{13}) = arccos(\frac{5}{13})$ .

There’s quite a lot of trigonometric fun packed into this little sum. And there’s still more to do, like exploring different phase shifts and trying the cosine angle sum formula instead. Enjoy!

Related Posts

By MrHonner, 7 years7 years ago

Challenge Numbers

The 2017-18 Conjecture

Like many mathematicians and teachers, I often enjoy thinking about the mathematical properties of dates, not because dates themselves are inherently meaningful numerically, but just because I enjoy thinking about numbers.

A new year means a new number to think about. And one interesting fact about our new year, 2018, is that it is semiprime.

A number is semiprime if it is the product of exactly two prime factors: for example, 15 = 3 * 5 is semiprime, as is 49 = 7 * 7, but neither 13 nor 30 are. Semiprime numbers are also referred to as biprime, 2-almost prime, or pq–numbers.

Semiprimes are very interesting in and of themselves, particularly in cryptography, but what caught my attention is that the previous year, 2017, is a prime number. That means we have a semiprime number, 2018, adjacent to a prime number, 2017. How unusual is this?

I played around a bit and ended up writing some simple programs to find and analyze semiprimes. Among the first 500,000 integers, there are roughly 108,000 semiprimes and 41,500 primes. Of the 108,000 semiprimes, only about 2,500 (or 2.3%) are adjacent to a prime number. This seems low to me: there are 83,000 prime-adjacent spots among the first 500,000 integers, representing 18% of the spots semiprimes could occupy. But only about 2.3% of the 108,000 semiprimes end up in those spots. That seems unusual. * [See Update]

In thinking about what happens further out along the number line, I couldn’t help but wonder if there are infinitely many prime-semiprime pairs like 2017 and 2018. I certainly don’t know the answer, but I thought I would start the new year boldly, with a conjecture:

The 2017-18 Conjecture

There are infinitely many pairs of consecutive integers one of which is prime and one of which is semiprime.

I think this problem’s resemblance to the Twin Prime Conjecture led me to both imagine this conjecture and also suspect it’s true. As with virtually everything in mathematics, I’m sure someone has thought of this before, and I would love a reference if anyone can provide it.

Thinking ahead, I was excited to notice that next year will also be a semiprime!

But it appears that the Twin Semiprime Conjecture is already an existing open question, which means I have less than a year to come up with a new conjecture for 2019.

Happy New Year! 2018 has already inspired to me to do some number theory, tackle some computing challenges, and think about some new ideas for the classroom. It’s a good mathematical start to the new year, and here’s hoping 2018 only gets better.

UPDATE, 1/18/2018

In a comment, Brent pointed out that I undercounted the number of semiprimes adjacent to a prime. A recalculation is consistent with Brent’s numbers: among the 108,000 semiprimes up to 500,000, around 4,900 of them are adjacent to prime number. Thanks, Brent!

Related Posts

By MrHonner, 7 years7 years ago

The 2017-18 Conjecture

There are infinitely many pairs of consecutive integers one of which is prime and one of which is semiprime.

Follow Mr Honner