Difference of Squares (1)

In general, all odd positive integers, except 1, and all multiples of four, except 4 itself, may be written as the difference of non-zero perfect squares.

Thus, $\boxed{18}$ is the exception.

For the other values, we have $\begin{cases} 16 = 5^2 - 3^2 \\ 17 = 9^2 - 8^2 \\ 19 = 10^2 - 9^2 \\ 20 = 6^2 - 4^2 \\ 21 = 11^2 - 10^2 = 5^2 - 2^2 \end{cases}$

Proof: Let $N$ be a number and $ab = N$ , where $b > a$ . (Such numbers $a$ and $b$ exist unless $N = 1$ .)

Let $d = \tfrac12(b - a)$ and $s = \tfrac12(b + a)$ . Then $N = ab = (s - d)(s + d) = s^2 - d^2.$ However, if $a$ and $b$ have different parity (one is even, one is odd), then $s$ and $d$ are not integers. This situation never happens if $N$ is odd.

For even $N$ , there are two scenarios. If $N$ is a multiple of four, we can always choose $a$ and $b$ to be both even (unless $N =4$ , because then $a = b = 2$ ); but if $N$ is even but not a multiple of four, this is impossible.

We want to know the number of integers $x$ which can be written as

$x = a^2 - b^2$

where $a > b$ .

Let's break this up and look at two sets of numbers: odd and even.

If $x$ is an odd number, it can be written as $2n + 1$ . Now consider the number $(n + 1)^2$ , or $n^2 + 2n + 1$ . We can use that to express $2n + 1$ in a different way.

$2n + 1 = (n + 1)^2 - n^2$

This proves that every odd number can be written as the difference of two squares. In fact, adjacent squares are separated by successive odd numbers.

Thus, $17 = 9^2 - 8^2$ and $19 = 10^2 - 9^2$ can be written as the difference of two positive perfect squares.

Now let's account for the even numbers. First, we know that $a^2 - b^2 = (a + b)(a - b)$ . Let's consider 3 cases relating to the parity of $a$ and $b:$ $a$ and $b$ are both even, both odd, or one of each.

Both even $:$ $a \pm b$ is even, $(a + b)(a - b)$ is even

Both odd $:$ $a \pm b$ is even, $(a + b)(a - b)$ is even

Even, odd $:$ $a \pm b$ is odd, $(a + b)(a - b)$ is odd

We can ignore the last option, since we've already taken care of the odd numbers.

Any product of two even numbers has to be divisible by $4 -$ this is because the product will have at least two $2$ s in its prime factorization. But the even numbers that cannot be evenly divided by $4 - 2, 6, 10,$ and so on $-$ cannot be written as the product of two even numbers. These numbers therefore cannot be written in the form $(a + b)(a - b),$ which also means that they cannot be written as the difference of two squares.

But is the converse $-$ that all the even numbers divisible by $4$ can be written as the difference of two squares $-$ necessarily true? Yes, because if $x$ is a multiple of $4,$ it equals $4n$ for some number $n$ , and $4n$ can be rewritten as: $(n + 1)^2 - (n - 1)^2.$

Thus, $16 = 5^2 - 3^2$ and $20 = 6^2 - 4^2$ can be written as the difference of two positive perfect squares.

$\boxed{18}$ , being neither odd or a multiple of four, cannot be written as the difference of two positive perfect squares.

$x^2 \equiv 0 \text{ or } 1 \mod{4} \implies a^2 -b^2 \equiv 0, 1, \text{or} 3 \mod{4} \implies a^2 -b^2 \neq 4k+2 \implies a^2 -b^2 \neq 18$ .

From the below table it is clear that 18 cannot be written as the difference of two positive perfect squares . In general, if 'N' is the number and the number can represented as factor pairs in the form (a,b). If any of its factor pair both a & b are odd numbers (or) both a & b are even numbers then the given number 'N' can written as the difference of two positive perfect squares.

$N=ab=(x+y) (x-y)= x^2 - y^2$ , where $a, b$ are factors of $N$ and $x = \frac{\text{sum of}\ a\ \text{and}\ b}{2}$ , $y=\frac{\text{difference of}\ a\ \text{and}\ b}{2}\$ . Then, the given number 'N' can written as the difference of two positive perfect squares satisfy the condition x and y must whole number iff both a and b are odd numbers (or) both a and b are even numbers.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

# -*- coding: utf-8 -*-
"""
Created on Tue Nov 28 17:24:09 2017

@author: Michael Fitzgerald
"""
numbs = []
top_limit = 30

items = [x for x in range(1,top_limit+1)]
pairs = [[items[i],items[j]] for i in range(len(items)) for j in range(i+1, len(items))]

for i in pairs:
    sq_diff = i[1]**2-i[0]**2
    if sq_diff not in numbs:
        numbs.append(sq_diff)

candidates = ','.join(str(e) for e in sorted(list(set(items)-set(numbs))))

print "Numbers in range 1-%d that cannot be be formed from the difference of perfect squares: %s" \
    % (top_limit, candidates)

Numbers in range 1-30 that cannot be be formed from the difference of perfect squares: 1,2,4,6,10,14,18,22,26,30

Every odd integer can be expressed as the difference of perfect squares, according to a simple pattern. The difference of 1 and 4 is 3; the difference of 4 and 9 is 5; the difference of 9 and 16 is 7, and so on. We can prove this by expressing the difference of two pairs of perfect squares. $n^ 2 - (n - 1)^ 2 = n^ 2 - n^ 2 + 2n - 1 = 2n - 1. (n+1)^ 2 - n^ 2 = n^ 2 - n^ 2 + 2n + 1 = 2n + 1.$ 2n + 1 is 2 more than 2n - 1, and both express odd numbers. By math induction, if we plug in 2 for n and get 3 (which we do), we will get all subsequent odd numbers. This allows to to check off 17 and 19.

Because of this property, we know that a number is the difference of perfect squares if and only if it can be expressed as the sum of any number of consecutive odd integers. For example, 16 is the sum of 7 + 9, so we can check it off. We now only need to check 20 and 18. They must be expressed either as the sum of two or four consecutive odd integers. 20 can be expressed as 9 + 11. 18 cannot be expressed as the sum of two or four consecutive odd integers; therefore, 18 is out.

General rule for finding integer solutions for x and y where A = (x^2) - (y^2)

As long as we can show that at least ONE solution for A exists, we need not consider further solutions for the same A for the purposes of this question.

A = (x^2) - (y^2) = (x+y)(x-y) so A has the factors: (x+y) and (x-y). As we are looking for "the difference of 2 positive perfect squares", both x and y MUST be integers. A is defined as an integer, and can only be either even or odd.

Prime A:

If A is prime, then, as there are only two factors (A and 1), then, we must concede that:

x+y = A

x-y = 1

solving these simultaneous equations:

2x = (A+1)

x = (A+1)/2

so y = x-1 = (A+1)/2 - 1 = (A-1)/2

If A = the only even prime, 2,

x+y = 2

x-y = 1

2x =3

=> x=1.5 and y=0.5

As x and y are not integers, A=2 CANNOT be re-written as the difference of 2 positive perfect squares.

If A = an odd number (which will include all of the remaining, odd, primes):

let A=2k+1 where k is an integer:

x+y = 2k+1

x-y = 1

2x = (2k+1+1); x = (2k+2)/2 = k+1 (integer)

so y = x-1 = (k+1) - 1 = k (integer) so for any A = 2k+1 = (k+1+k)(k+1-k) = (k+1)^2 - k^2 = 2k+1

so for ANY odd A, it CAN be re-written as the difference of 2 positive perfect squares. There will be at least one possible solution.

All odd A?: Yes

Even A=2?: No

what about for even values of A >2 ?

Let A=2w where w is an integer. ie '2' and 'w' are factors of even A. from the above (A cannot=2) w must >=2

As above:

x+y = w

x-y = 2

2x = w+2 =>

x = (w+2)/2 = (w/2)+1

y = x-2 = (w/2)+1-2 = (w/2)-1

A = x^2 - y^2 = [(w/2)+1]^2 - [(w/2)-1]^2 = [(w/2)^2 + 2(w/2) + 1] - [(w/2)^2 - 2(w/2) + 1] = 4(w/2) = 2w = A, as expected.

BUT both x and y must be integers. (w/2) +/- 1 will only be an integer if w is EVEN. If w is even, then w=2m where m is an integer. => A = 2w = 4m

So if A is divisible by 4, then there WILL be a possible solution

From the above, it appears to show that if A=2w where w is odd, then there is no possible solution. But the above only describes the cases where x-y = 2. Given that (x+y) and (x-y) are factors of A, the same A may give several different possible factor pairs. In the case of A=2p where p is prime, (x-y) MUST = 2. So for any A=2p (p>2), there can be no solution. But what if x-y is not 2, but a larger number?

If A=2gh where g and h are prime, possible factorisations are:(1)(A), (2)(gh), (2g)(h), (2h)(g). If g and h are composite, the number of factors increases further. But we are only interested in factors where A=2w where w is odd, as we have already dealt with the case of even w.

To obtain an odd number, through multiplication, we can only have odd numbers multiplied together. Any even number introduced will make the answer even too. So if we say we have a composite ODD w, its factors, no matter how many they are, MUST also be odd.

let A=(x+y)(x-y) = (2n)(t) where both n and z are odd integers, w=nt

n and t may be prime or composite. it doesn't matter which. Here it only matters that they are odd. If A=2w and w is odd, any possible remaining solution for A, MUST have its factors in the form (2n)(t). We have already dealt with the case of 2(nt) (=2 times odd).

Either:

1) (x+y)=2n ; (x-y)=t OR

2) (x+y)=t ; (x-y)=2n

1)

x+y = 2n

x-y = t

2x = 2n+t =>

x=(2n+t)/2 = n+(t/2)

y= x-t = n+(t/2) - t = n-(t/2)

2)

x+y = t

x-y = 2n

2x = 2n+t =>

x = (2n+t)/2 = n+(t/2)

y= x-2n = n+(t/2)-2n = (t/2)-n

In both these cases x = n+(t/2) but t, from above, HAS to be odd, which as n is an integer means that x cannot be an integer, but it must be! This contradiction shows, therefore, that no possible solution exists when A=2nt, n and t both odd.

So, to summarise: If A is ODD, SOLUTIONS ARE POSSIBLE

If A is PRIME >2, ONLY ONE SOLUTION POSSIBLE: [ (A+1)/2 ]^2 - [ (A-1)/2 ]^2

If A=2: NO POSSIBLE SOLUTION

If A=2w, where w is an ODD value, NO POSSIBLE SOLUTION

If A=2w, where w is an EVEN value, (or A=4m), SOLUTIONS ARE POSSIBLE

A

16 = 4n ==> SOLUTIONS POSSIBLE [5^2 - 3^2]

17 = prime ==> ONLY ONE SOLUTION POSSIBLE [9^2 - 8^2]

18 = 2(odd number) ==> NO SOLUTION POSSIBLE <----------

19 = prime ==> ONLY ONE SOLUTION POSSIBLE [10^2 - 9^2]

20 = 4n ==> SOLUTIONS POSSIBLE [6^2 - 4^2]

Firstly write down all the squares of numbers 1 to 10.
As :- 1,4,9,16,25,36,49,64,81,100. Now, 25 - 9 = 16 ; 81 - 64 = 17 ; 100 - 81 = 19 ; 36 - 16 = 20 ; Hence, we cannot write 18 as a difference of any squares of positive numbers.

Notice from the squares 1,4,9,16... They differ by 3,5,7... This rules out all odd entries. If we observe the differences of every other square, they're the sum of neighboring odds (9-1=8=5+3 or 16-4=12=7+5). This rules out all even entries that are, after dividing by 2, even. This removes 16 and 20. Left with 18, we check for sanity it cannot be written as (2 + n) + (n) for odd n. It cannot, therefore 18 cannot be written as a difference of squares.

For $n=a^2-b^2$ , where $n,a,b \in \mathbb N$ and $a>b$ , we have:

$\begin{aligned} n & = a^2 - b^2 & \small \color{#3D99F6} \text{Let }n = pq \text{, where }p<q \text{ are factors of }n. \\ pq & = (a-b)(a+b) & \small \color{#3D99F6} \text{Equating }p = a-b \text{ and }q=a+b \end{aligned}$

$\begin{cases} p = a-b \\ q = a+b \end{cases} \implies \begin{cases} a = \dfrac {p+q}2 \\ b = \dfrac {q-p}2 \end{cases}$

Now for $a$ and $b$ to be integers, $p$ and $q$ must be either both odd or both even. Since $n=pq$ , $n$ that yields solution must be either odd (when both $p$ and $q$ are odd) or a multiple of 4 (when both $p$ and $q$ are even). Since 18 is neither odd nor a multiple of 4, it cannot be expressed as a difference of two perfect squares.

The difference between the squares of $N$ and $N+1$ is $2*N+1$

So all odd numbers greater than 3 can be written as the difference the squares of two positive sequential numbers.

$15=64-49=8^2-7^2$

$17=81-64=9^2-8^2$

$19=100-81=10^2-9^2$

For even numbers you need to check if they can be written as a sum of sequential odd numbers.

$16=7+9$

that are the differences between the squares of 3 to 4 and 4 to 5. That means 16 can be written as $16=25-9=5^2-3^2$

$20=9+11$

that are the differences between the squares of 4 to 5 and 5 to 6. That means 20 can be written as $20=36-16=6^2-4^2$

That leaves $\boxed{18}$ as the only number in the possible answers that can't be written as a difference of two squares

Consider perfect squares 1,4,9.16,25,36,49 have a difference of 3,5,7,9,11,13,...

16 = 7+9 = 25 - 9

20 = 9+11 = 36 -16

18 is an even number, and it cannot be expressed as the sum of two or more consecutive odd numbers,

thus it cannot be written as the difference of two positive perfect squares.

We know that the difference between adjacent squares is odd, e.g. 9-4=5, 16-9=7. These differences form all positive odd numbers. This immediately discounts 17 and 19.

Consequently, the difference between non-adjacent squares is the sum of 2 or more adjacent odd numbers. We can simply see that 16=9+7 and 20=11+9.

18 is the number that can't be written like this, so for the purposes of this question, that is the answer.

It is straightforward to generalise this argument that even numbers need to be a multiple of 4 in order to be the difference between squares.

A $n^2$ is the sum of the $n$ first odd integers: $n^2 = \sum_{i=1}^n (2i-1)$ So any difference of squares is a sum of consecutive odd numbers. Let's split in cases:

Case 1: there is only one odd number. Then we've got all odd numbers. (This includes 17 and 19).

Case 2: there are two consecutive odd numbers. The first possibility is 1+3 = 4. Note that the next possibility is 3+5 = 8. Successive possibilities add 4 to the whole sum. So we have all multiples of 4. (This includes 16 and 20).

Remaining cases: The sum of three consecutive odd numbers is odd, so we don't care anymore (they have the form $9 + 6k$ ). So we move on to 4 consecutive odd integers. The first is 16 and the next 24. At five or more consecutive odd integers we arrive at 25 or more which is too big.

PS: One could directly write $(m+k)^2-m^2 = m^2 + 2mk$ ( $k$ is then the number of consecutive odd integers). With $m = 1,2,3$ or $4$ one gets the above forms.