I submitted solutions for 30 problems of Nieuw Archief voor Wiskunde:

2005-2/C, 2006-4/AB, 2007-1/AB, 2007-2/C, 2007-4/A, 2008-1/A, 2011-3/A, 2014-1/C, 2014-3/ABC, 2014-4/A, 2015-2/A,
2015-3/ABC, 2015-4/A, 2016-1/C, 2016-2/(A)B(C), 2017-1/AC, 2017-2/A, 2017-3/A(C), 2017-4/ABC, 2018-1/A(BC).

Most of them have already been recognized by NAW.

Here are some of them, and some partial solutions.

I received book tokens for 2011-3/A, 2014-3/C, 2015-3/C, 2016-2/C and 2017-4/A.

**Problem 2011-3/A**

*Fix a point P in the interior of a face of a regular tetrahedron Δ. Show that Δ can be partitioned into four congruent convex polyhedra such that P is a vertex of one of them.*

__Solution:__

Let A,B,C,D be the vertices of Δ and suppose P is an arbitrary point in the interior of face ABC.

P is determined by its distances λ, μ, ν to A,B,C resp.

Let us fix three more points so that on each face we have one of the four fixed points and each of A,B,C,D is at distance λ from one of them, at distance μ from another one, and at distance ν from
a third one:

Let T_{ABC} be the point on face ABC at distances λ, μ, ν to A,B,C resp. (So T_{ABC} = P.)

Let T_{BCD} be the point on face BCD at distances λ, μ, ν to C,D,B resp.

Let T_{CDA} be the point on face CDA at distances λ, μ, ν to D,C,A resp.

Let T_{DAB} be the point on face DAB at distances λ, μ, ν to B,A,D resp.

So δ := T_{ABC}T_{BCD}T_{CDA}T_{DAB} is also a regular tetrahedron. Let O be its center.

Now we will allot points of Δ to each X ∈ {A,B,C,D} in such a way that the points allotted to X form a convex polyhedron, and such that the four polyhedra are congruent and form a partition
of Δ.

The allotment will first be done in two steps:

Step 1)

The points in the hexahedron AT_{ABC}T_{CDA}T_{DAB}O belong to A.

The points in the hexahedron BT_{ABC}T_{BCD}T_{DAB}O belong to B.

The points in the hexahedron CT_{ABC}T_{BCD}T_{CDA}O belong to C.

The points in the hexahedron DT_{BCD}T_{CDA}T_{DAB}O belong to D.

Step 2)

To allot the remaining points in the interior of Δ while preserving convexity and congruence, we extend (to the exterior of δ)
the six planes through O and a side of δ that bisect the angles between two faces of δ.

Through each vertex of δ there go three of these bisectrix planes.

Now for each X ∈ {A,B,C,D}, allot to X all remaining points y ∈ Δ such that, for each plane through O and a side of the nearest face of δ,
X and y are at the same side of that plane.

Of course, we can sum it all up, including both steps 1 and 2, as follows:

For each X ∈ {A,B,C,D}, allot to X all points y ∈ Δ such that, for each plane through O and a side of the nearest face of δ,
X and y are at the same side of that plane.

**Problem 2013-2/A revised (to make it a bit simpler)**

*We have two hourglasses, A for a seconds and B for b seconds, where a and b are relatively prime positive integers.
Let t be an integer with t ≥ ab. Show that A and B can be used to identify the time t if the upper bulbs are empty at the start.*

__Solution:__

We will find non-negative integers p and q such that pa + qb = t, which is clearly sufficient for our purpose, as follows;

Since a and b are coprime, there exist positive integers m and n such that mb - na = 1 (or mb - na = -1, then reverse the roles of a and b).

So for any positive integer s we have (tm-sa)b + (sb-tn)a = t.

If we can find such s within [tn/b,tm/a] = [tn/b, tn/b + t/ab], we can take p = tm-sa, q = sb-tn, and then we are finished.

Now if t ≥ ab, then this interval has length ≥ 1, so then we can find in it this positive integer s.

**Problem 2014-4/A **

*Let k be an integer, at least 4. Determine the variance of the greatest common divisor of k positive integers.
Here we mean the limit, as n → ∞, of the variance of the greatest common divisor of k integers in {1,2,...,n} with respect to the uniform distribution on {1,2,...,n} ^{k}.*

__Solution:__

We find the probability that d is gcd is (1/d^{k})*Π_{p prime}(1 - 1/p^{k}) = 1/(d^{k}*ζ(k)).

So the expectation value of the gcd is Σ_{d=1}^{∞} d/(d^{k}*ζ(k)) = ζ(k-1)/ζ(k).

So the variance of the gcd is Σ_{d=1}^{∞} (d - ζ(k-1)/ζ(k))^{2}/(d^{k}*ζ(k)) =
(ζ(k)*ζ(k-2) - ζ(k-1)^{2})/ζ(k)^{2}.

(The formula for the probability means: that the k integers are divisible by d and, after division by d, for each prime p, not all of them divisible by p.)

**Problem 2016-1/C**

* Determine all two-sided infinite sequences of positive integers in which each number is the Euler-φ of the next.*

__Solution__

If n has prime factorization p_{1}^{a1}p_{2}^{a2}...p_{k}^{ak} then
φ(n) = p_{1}^{a1-1}p_{2}^{a2-1}...p_{k}^{ak-1}(p_{1}-1)(p_{2}-1)...(p_{k}-1).

Since for n larger than 1 we find φ(n) smaller than n, such a sequence must begin with infinitely many 1's.

We may terminate these 1's at the left hand side of the sequence by replacing the last 1 by 2, which is the only other number whose φ is 1.

If we do that, then in the next position after 2 we can put only 2^{2} or 2*3. We can't put 3, because there would be no option for the next position after the 3.

Now if at some position we have 2^{s}, then in the next position we can only put 2^{s+1} or 2^{s}3.
For example, we can't put 2^{s-1}5 or 2^{s-3}17, for, going further to the right, we would soon run out of factors 2.

And if at some position we have 2^{s}3^{t}, then in the next position we can only put 2^{s}3^{t+1}. For example, we can't put there 2^{s-1}3^{t}7,
because we would again run out of options for lack of factors 2 after a few steps to the right.

So this sums up all possible sequences.

**Problem 2016-2/B**: Suppose there are N ≥ 2 players, labeled 1,2,..,N, and each of them holds precisely m ≥ 1 coins of value 1, m coins of (integer) value n ≥ 2, m coins of value n^{2}, etc.

A transaction from player i to player j consists of player i giving a finite number of his coins to player j.

We say an N-tuple (a_{1},a_{2}, ... ,a_{N}) of integers is (m,n)-payable if Σ_{i=1,2,..,N} a_{i} = 0 and after a finite number of transactions the
i-th player has received (in value) a_{i} more than he has given away.

Show that for every N-tuple (a_{1},a_{2}, ... ,a_{N}) with Σ_{i=1,2,..,N} a_{i} = 0 to be (m,n)-payable, it is necessary and sufficient that
m > n - n/N - 1.

**Solution**

The inequality can be rewritten as (n-1)(N-1) ≤ mN.

This is the necessary and sufficient condition that for each k the mN coins can be redistributed so that all but one players at the end have up to n-1 coins of worth n^{k} for each k,
thus covering in the n-ary system all values of possession.

(The player who paid the most holds the rest of the total value.)

**Problem 2016-2/C**: For each integer n ≥ 1, let c_{n} be the largest real number such that for any finite set of vectors X ⊂ ℜ^{n} with Σ_{v∈X} |v| ≥1
there exists a subset Y ⊆ X with |Σ_{v∈Y} v| ≥ c_{n}.

Prove the recurrence relation c_{1} = 1/2, c_{n+1} = 1/(2πn c_{n}).

**Solution:**

For each n we seek X ⊂ ℜ^{n} with Σ_{v∈X} |v| ≥1 for which the maximum of |Σ_{v∈Y} v| with Y ⊆ X is as small as possible.

For this we consider X consisting of an even number of vectors of equal length whose directions are as distinct as possible and whose lengths add up to 1.

The corresponding best Y consists of the half of these vectors whose directions are as much the same as possible.

For n=1 we consider X = {1/2,-1/2} and Y={1/2}. We find c_{1} = 1/2.

For n=2 we consider X consisting of 2m vectors (cos(kπ/m),sin(kπ/m))/(2m), k=0,1,..,m-1,m,..,2m-1, and Y consisting of the first m of these vectors of X, so with k=0,1,..,m-1.

We use complex numbers to calculate c_{2} and find |Σ_{k=0,..,m-1} e^{ikπ/m}|/(2m) = |(e^{imπ/m} - 1)/(e^{iπ/m} - 1)|/(2m) =
1/(2m sin(π/(2m))) → 1/π = c_{2} for m → ∞.

Now it's sufficient to prove c_{n+2} = (n/(n+1)) c_{n}.

The step from X and Y in ℜ^{n} to X' and Y' in ℜ^{n+2} can be made by replacing each of all p vectors v ∈ X (of length 1/p) by 2m vectors
v' = (pnv/(n+1) + (√(2n+1)/(n+1))(cos(kπ/m)e_{m+1} + sin(kπ/m)e_{m+2}))/(2pm), k=0,1,..,2m-1, (of length 1/(2pm) = 1/p'), where the e_{i} form the orthonormal base in
ℜ^{n(+2)}. Then Σ_{v'∈Y'} v' = (n/(n+1)) Σ_{v∈Y} v.

Explanation of the factor n/(n+1) in pnv/(n+1):

When making new directions by adding orthogonal adjustments to the old directions, in order to keep the directions as distinct as possible (so having maximal variance),
we must weigh the old direction vectors with factor cos(ψ) = n/(n+1). Then sin(ψ) = √(2n+1)/(n+1).

**Problem 2016-4/A**: For a finite sequence s = (s_{1}, s_{2}, ... , s_{n}) of positive integers, denote by p(s) the number of ways to write s as a sum
s = Σ_{i=1}^{n} a_{i}e_{i} + Σ_{j=1}^{n-1} b_{j}(e_{j}+e_{j+1}) with all a_{i} and b_{j} non-negative.

Here e_{i} denotes the sequence of which the i-th term is 1 and of which all the other terms are 0.

Show that there exists an integer B > 1 such that for any product F of (positive) Fibonacci numbers, there exists a finite sequence s = (s_{1}, s_{2}, ... , s_{n}) with all
s_{i} ∈ {1,2,..,B} such that p(s) = F.

**Partial solution:**

If n=1 we only have the equation a_{1} = s_{1}, so p(s)=1.

If n=2 we only have the equations a_{1} = s_{1} - b_{1}, a_{2} = s_{2} - b_{1}, so 0 ≤ b_{1} ≤ min(s_{1},s_{2}) and
p(s) = min(s_{1},s_{2}) + 1.

This equals F iff min(s_{1},s_{2}) = F-1, but then the terms of s aren't bounded by an integer B > 1.

If n=3 we have a_{1} = s_{1} - b_{1}, a_{2} = s_{2} - b_{1} - b_{2}, a_{3} = s_{3} - b_{2}, so
p(s) = Σ_{b1=0}^{s1} Σ_{b2=0}^{min(s3,s2-b1)} 1.

If n ≥ 4 we have a_{1} = s_{1} - b_{1}, a_{2} = s_{2} - b_{1} - b_{2}, ... , a_{n-1} = s_{n-1} - b_{n-2}
- b_{n-1}, a_{n} = s_{n} - b_{n-1},
so p(s) = Σ_{b1=0}^{s1} Σ_{b2=0}^{s2-b1} ...
Σ_{bn-2=0}^{sn-2-bn-3} Σ_{bn-1=0}^{min(sn,sn-1-bn-2)} 1.

Especially, if s(n) is a row of n ones, we find: p(s(1)) = 1, p(s(2)) = 2, p(s(3)) = Σ_{b1=0}^{1} Σ_{b2=0}^{1-b1} 1 = 3,
and for n≥4

p(s(n)) = Σ_{b1=0}^{1} Σ_{b2=0}^{1-b1} ...
Σ_{bn-2=0}^{1-bn-3} Σ_{bn-1=0}^{1-bn-2} 1 = {taking b_{1} = 0 and b_{1} = 1} = p(n-1) + p(n-2).

So by induction we find p(s(n)) = F_{n}, that is the n-th Fibonacci number.

Now clearly if F = F_{t1}*F_{t2}* ... *F_{tk} is any product of k ≥ 1 Fibonacci numbers > 1, then F = p(s) where
s is the concatenation (s(t_{1}),0,s(t_{2}),0, ... , 0,s(t_{k})).

But how do we get rid of the zeroes?

**Problem 2017-1/A**: Reconstruction. Suppose you get to know the n midpoints of the n edges of a polygon.
Can you determine the polygon?

**Solution:**

Let the vertices of the polygon in the complex plane be denoted by a_{1}, a_{2}, ... , a_{n}, with n > 2.

Given z_{1} = (a_{1} + a_{2})/2, z_{2} = (a_{2} + a_{3})/2, ... ,
z_{n} = (a_{n} + a_{1})/2, we have to find a_{1}, a_{2}, ... , a_{n}.

With the usual method of solving linear equations, we find:

1) If n is odd, then a_{i} = z_{i} - z_{i+1} + z_{i+2} - ... + z_{i+n-1}
(i=1,2,..,n, indices modulo n).

2) If n is even then we must have z_{n} = z_{1} - z_{2} + z_{3} - ... + z_{n-1}, or the given
set of midpoints would be false. We have n-1 independent linear equations in a_{1}, a_{2}, ... ,a_{n}.
If we would take a_{n} = 2a as we like, we would find a_{n-1} = 2z_{n-1} - 2a,
a_{n-2} = 2z_{n-2} - 2z_{n-1} + 2a, ... , a_{1} = 2z_{1} - 2z_{2} +
2z_{3} - ... + 2z_{n-1} - 2a.

We conclude: if n is odd, we can reconstruct the original polygon, but if n is even we only find the original polygon
if we happen to take a = a_{n}/2, where a_{n} is the n-th vertex of the original polygon.

**Problem 2017-1/B**: Large is odd. Let G be a graph with vertices V and edges E. A subset U of V is called large
if every vertex that is not in U has a neighbour in U. Prove that the number of large subsets is odd.

**Partial solution:**

First notice that the number of large subsets is the product of the numbers of large subsets in maximal connected subgraphs. Therefore we need only consider the case that G is connected, which we henceforth assume.

Apart from the trivial cases wherein G has only one or two vertices, there is at least one vertex of degree greater than 1.

We are going to use induction to the number n of vertices of degree at least 2.

If n = 1 then G is a flower with 1 center v and k ≥ 2 leaves. In this case, every subset that includes v is large, and
the only large subset that doesn't include v must include all the end points of the leaves.
So the number of large subsets is 2^{k}+1, which is odd.

Now suppose the proposition is true if n ≤ m.

Consider a connected graph with n=m+1 vertices of degree greater than 1.

Put aside a vertex w of degree greater than 1 with a minimal number of connections to vertices of degree greater than 1,
together with the vertices of degree 1 w is connected to and all the edges with w as an endpoint.

By induction hypothesis, the remaining part of the graph has an odd number of large subsets. We are going to show that
if we put back the removed part then the following two facts hold so we can do the induction step:

1) Each of these large subsets of the remaining part can in an odd number of ways be strictly
extended to a large subset of the original graph.

2) The number of large subsets of the original graph whose restriction to the remaining part
is not large in the remaining part is even.

Indeed:

1) Such a strict extension can be made by either including w and excluding or including at random vertices of
degree 1 connected to it, or excluding w and including all vertices of degree 1 connected to it. This
yields the odd number 2^{k}+1 of strict extensions if there are k ≥ 1 vertices of degree 1 connected to w, and
the odd number 1 of strict extensions if there are no vertices of degree 1 connected to w.

2)

**Problem 2017-1/C**: Meanders. Let n be an even number. Consider the integers 1 to n in the complex plane and
connect them by semicircles with center (n+1)/2 in the upper half plane. Let n = a+b for even numbers a and b. Connect the
first a integers by semicircles around (a+1)/2 in the lower half plane. Similarly, connect the final b integers by
semicircles around a + (b+1)/2 in the lower half plane. The resulting curve or set of curves is a meander. For which a and b is
it connected?

**Solution:**

Let a=2p and b=2q and p ≥ q. Consider the following operations:

A) Connecting r with 2p+1-r for 1 ≤ r ≤ 2p (by drawing a semicircle below at the left hand side).

B) Connecting s with 2p+2q+1-s for 1 ≤ s ≤ 2p+2q (by drawing a semicircle above from the left to the right or
vice versa).

C) Connecting t with 4p+2q+1-t for 2p+1 ≤ t ≤ 2p+2q (by drawing a semicircle below at the right hand side).

Subsequently we perform an operation of type A or C and an operation of type B without taking the pencil from the paper,
starting at 1. The meander is connected if and only if we meet all numbers 1 to n this way.

We notice that if p and q have a common divisor d then by each operation we connect an integer u with an integer v where v = 1-u (mod d), so if u = 1 (mod d) then v = 0 (mod d) and vice versa. So, starting with 1, we meet only integers w that are congruent to 0 or 1 (mod d). So in this case, if d is greater than 2, the meander is not connected.

In general, starting with 1, we meet subsequently numbers that are congruent mod 2p+2q to: 1, 2p, 1-2p, 4p, 1-4p, 6p, etc. Now we meet all numbers 1 to n = 2p+2q if and only if the first n numbers in this sequence are distinct modulo 2p+2q. Since an even and an odd number can't be congruent modulo 2p+2q, this is only false if 2kp = 2mp (mod 2p+2q) and hence kp = mp (mod p+q) for some distinct k and m in the range from 1 to p+q. This occurs if and only if gcd(p,q) ≥ 2, so in this case the meander is disconnected. But if gcd(p,q)=1, the meander is connected.

**Problem 2017-2/A**:

Show that there are no infinite antichains for the partial order ≤ on ℵ^{k}
defined by (x_{1},x_{2},...,x_{k}) ≤ (y_{1},y_{2},...,y_{k}) iff
x_{i} ≤ y_{i} for all i, 1≤i≤k.

**Solution:**

Recall an antichain is a set S of at least two elements of ℵ^{k} such that any two distinct members p,q
of the set are incomparable, so neither p ≤ q nor q ≤ p.

Since ℵ^{k} is countable, the elements of S can be numbered s_{1}, s_{2}, ...

We proceed with induction.

If k=1 the partial order is total. Any two natural numbers p,q are comparable, so in this case there don't exist antichains, let alone
infinite antichains.

So the proposition holds for k=1.

Let k>1. Our induction hypothesis is that the proposition holds for each smaller k .

Assume there exists an infinite antichain S = {s_{1}, s_{2}, ...}. We have to show this contradicts the
induction hypothesis.

Because s_{1} is incomparable with each other element of S, for each s ∈ S there must exist i,j with
1 ≤ i, j ≤ k and i≠j such that s_{1}_{i} < s_{i} and
s_{1}_{j} > s_{j}.

Moreover, since S is infinite and {1,2,..,k} finite,
there must exist such i,j such that s_{1}_{i} < s_{i}
and s_{1}_{j} > s_{j} for infinitely many s.

But there are only finitely many natural numbers smaller than s_{1}_{j}, so there must exist an
infinite subset S' of S whose members all have the same j-th coordinate.

Now by taking the j-th coordinate away, we derive from S' an infinite antichain in ℵ^{k-1}, which
contradicts the induction hypothesis.

**Problem 2017 3-A**:

Let n be a natural number and suppose that A_{1}, A_{2}, ... , A_{n} are different subsets of
{1,2,...,n}.

Prove that there is a k ∈ {1,2,..,n} such that A_{1}\{k}, A_{2}\{k}, ... , A_{n}\{k} are
different.

**Solution:**

We use induction to n.

The statement is clearly true for n=1.

Now suppose the statement is true for some n.

Suppose A_{1}, A_{2}, ... , A_{n+1} are different subsets of {1,2,...,n+1}.

If A_{1}\{n+1}, A_{2}\{n+1}, ... , A_{n+1}\{n+1} are different, we are finished.

Otherwise, for one or more disjoint unordered pairs {i,j}, A_{i}\{n+1} and A_{j}\{n+1} are equal, whereas
one of A_{i} and A_{j} contains n+1 and the other doesn't.

By forgetting for a moment, for each of these pairs, one of the two equal sets A_{i}\{n+1} and A_{j}\{n+1},
we reduce the list to m ≤ n different subsets B_{1}, B_{2}, ... , B_{m} of {1,2,..,n}.

By induction hypothesis, there is a k ∈ {1,2,..,n} such that
B_{1}\{k}, B_{2}\{k}, ... , B_{m}\{k} are different. (Of course, this also holds if m < n.)

Now for each B_{p} that equals A_{i}\{n+1} = A_{j}\{n+1} for distinct i and j,
A_{i}\{k} and A_{j}\{k} are different since one of them contains n+1 and the other doesn't.

So A_{1}\{k}, A_{2}\{k}, ... , A_{n+1}\{k} are different.

Notice that by looking at the complements we can prove a similar statement with '∪' instead of '\'.

**Problem 2017 3-C**:

Determine all n ∈ ℕ such that 2^{n}-1 divides 3^{n}-1.

**Partial solution:**

First we see that n=1 is a solution. We want to show it's the only solution.

Suppose n > 1 and 2^{n}-1 divides 3^{n}-1.

If n is even then 2^{n}-1 is divisible by 3, whereas 3^{n}-1 is not, so n must be odd.

In general, if 2^{n}-1 is divisible by some prime q and 3^{n}-1 is not, then n can't be a solution.

For instance, if n is a multiple of 3, and hence congruent to 3 mod 6 since n is odd, then 2^{n}-1 is
divisible by 7, whereas 3^{n}-1 is not, so n can't be a multiple of 3.

If n is a multiple of 5, and hence congruent to 5 mod 30 or to 25 mod 30 since n is no multiple of 2 and no multiple
of 3, then 2^{n}-1 is divisible by 31, whereas 3^{n}-1 is not, so n can't be a multiple of 5.

If n is a multiple of 7, and hence congruent to 7 mod 42 or to 35 mod 42 since n is no multiple of 2 and no
multiple of 3, then 2^{n}-1 is divisible by 127, whereas 3^{n}-1 is not, so n can't be a multiple of 7.

I think we can continue with induction as follows:

Assume n is not divisible by the first k primes, and let p be the k+1-st prime.

Suppose n is a multiple of p, so p is the smallest prime divisor of n.

For statistical reasons, there must exist some prime q with p dividing q-1 such that 2^{n}-1 is divisible by q,
whereas 3^{n}-1 is not divisible by q.

So n can't be divisible by p, either.

So with induction we conclude that n can't be divisible by any prime.

**Problem 2017-4/A**:

Consider two identical bags of stones, all having integral weights. No two weights in a bag are the same.
Suppose that the stones from these two bags are divided into proper subsets of equal cardinality and equal total weight.
No two weights in a subset are the same. Is it then possible to readjust this division so that each subset contains only
stones from the same bag?

**Solution:**

This is not always possible.

For instance, let each bag contain stones of weights 1,2,3,4,5,6.

If we divide the twelve stones from the two bags into three subsets of cardinality four and total weight fourteen,
without putting two stones of equal weight in the same subset, then these
subsets can only contain stones of weights 1,2,5,6 and 1,3,4,6 and 2,3,4,5, respectively.

But then at least one of these subsets must contain two stones from either bag.

**Problem 2017-4/B**:

Let H_{1}, H_{2}, ... , H_{k} be k planes in R^{3}. Prove that the unit ball contains
an open ball of radius 1/(k+1) which does not intersect any of the planes.

**Solution:**

The planes divide the unit ball in one or more parts. The maximal radius of an open ball in such a part that doesn't intersect any of the planes is minimal iff the planes are all parallel and divide the diameter they are perpendicular to in k+1 equal segments. Then this radius is 1/(k+1).

**Problem 2017-4/C**:

Suppose that a,b,n,m are integers, and that m,n are positive, such that
a^{n} ≡ b^{n} ≡ -1 mod m.

Prove there exists an integer c such that ab ≡ c^{2} mod m.

Also provide a fast method to compute such c which works even if the prime factors of m are unknown.

**Solution:**

First we note that gcd(a,m)=gcd(b,m)=1.

Suppose ab is a nonresidue mod m. Gausz already showed then one of the following two must hold:

1) either there exists an odd prime p dividing m such that ab is a nonresidue mod p

2) or there exists a positive integer d such that 2^{d} divides m and ab is a nonresidue mod 2^{d}.

We will derive contradictions in both cases.

1) In the first case:

Let δ be a primitive element of GF(p), so -1 = δ^{(p-1)/2} and without loss
of generality a = δ^{2k+1}, b = δ^{2j} for some nonnegative integers k and j.

Then there must exist nonnegative integers s and t such that (2k+1)n = (2s+1)(p-1)/2 and 2jn = (2t+1)(p-1)/2.

But here the right hand sides have the same number of factors 2, whereas the left hand sides don't.

2) In the second case:

If d=1 then ab can't be a nonresidue mod 2^{d}.

If d=2 then, since gcd(a,m)=gcd(b,m)=1, if ab is a nonresidue mod 2^{d} we have ab ≡ 3 mod 4.

Hence a or b must be congruent to 1 mod 4, which contradicts a^{n} ≡ b^{n} ≡ -1 mod 4.

If d≥3 then from a^{n} ≡ b^{n} ≡ -1 mod 8 we find a ≡ b ≡ 7 mod 8,
but then ab is a quadratic residue mod 2^{d}.

We may always find c by trying c = 0,1,2,... We need at most 1 + m/2 trials.