When asked to show a math problem has a unique solution, students sometimes think that if an algorithm leading to a solution has unambiguous instructions at each step (no need to make choices at any point) then the solution they find has to be the only solution. Loosely speaking, if each step in reaching the solution is "unique" then the end result has to be unique (the only possible solution).

This is not true, and I think it would be nice to have a list of examples at different levels (of undergraduate mathematics) showing why this idea is mistaken.

For example, if asked to solve $55x+32y = 1$ in integers then Euclid's algorithm for computing $\gcd(55,32)$ followed by back-substitution (reversing the steps of Euclid's algorithm) is a procedure where each step is completely determined by the previous ones and leads to the definite answer $(x,y) = (7,-12)$, but the original equation has infinitely many integral solutions: $(x,y) = (7+32t,-12-55t)$ for integers $t$.

What other examples can people offer? I am not interested only in computational problems.

• Solving the equation $\textbf{A}\cdot\textbf{X}=k$. Of course $\textbf{X}=\frac{k}{\textbf{A}^2}\textbf{A}$ is a solution among infinitely many others. – user5402 Oct 23 '17 at 17:35
• I think the most intuitive place to talk and think about this is in ODEs. I would actually not stress the concept itself too early, and especially as a general idea. But just bring it up when it is important for a particular topic. – guest Sep 19 '18 at 21:44

To find a basis for the row space of a matrix, perform elementary row operations to get to reduced row-echelon form. The nonzero rows of the row-reduced matrix are a basis for the row space of the original matrix.

But of course many other bases are possible (with an exception of the zero matrix).

Edited to address a commenter's request: It is true that the steps to row reduce a matrix are not unique (or uniquely ordered); however,

(1) It is possible to give an algorithmic specification of row reduction to reduced row-echelon form for matrices (i.e., no choices); and

(2) The reduced row-echelon form of a matrix is unique. So if we use row reduction as a method to get a basis for the row space of the original matrix, we will all get the same reduced row-echelon form, and hence the same basis, even if some of us do different steps (or steps in a different order) than others of us.

A "non-mathematical" answer: If you are in need of a doctor, then one unambiguous algorithm for finding one is to call everyone in the phone book, in order, and ask them if they are a doctor. Eventually you will find one. However, this does not imply there is only one doctor in your city.

• The OP specifies "no need to make choices". Perhaps "first one" is a method of making a choice. – Gerald Edgar Oct 24 '17 at 18:53
• @GeraldEdgar I don't think this is the sense in which OP meant "no need to make choices". My algorithm is deterministic. If I said "go in alphabetical order, and flip a coin. If heads: ask if they are a doctor. If tails: ask if their refrigerator is running", then I could see the complaint. – Steven Gubkin Oct 24 '17 at 19:20

Often students wrongly believe that integer factorization is unique because there is a deterministic algorithm for factorization: simply continue to pull out the least prime factor (found by trial division). To help them debunk this belief it suffices to show them another ring where a similar method fails. An elementary example is factoring (monic) quadratics with coefficients being integers $\!\bmod m.\,$ Here - as above - there is a simple deterministic factorization algorithm: simply test in order $r\equiv 0,1,\cdots,m-1$ till we find a root $\,r\,$ hence a factor $\,x-r\,$ (by the Factor Test).

But here factorization need not be unique, e.g. $(x-1)(x+1) \equiv (x-3)(x+3)\,\pmod{\! 8}$

Applying the above algorithm would find only the first factorization. This shows clearly and simply that the existence of deterministic algorithm for solution does not imply that the solution is unique.

• This is a nice suggestion, although I would prefer to stick to integral domains rather than something like $(\mathbf Z/8\mathbf Z)[x]$ so you have cancelation of elements. A non-UFD with finitely many elements of each norm, like $\mathbf Z[\sqrt{-5}]$, serves this role well. I'm teaching a number theory course now and began discussing unique factorization today, so the timing of your reply ahead of my next lecture is good. Thanks! – KCd Sep 19 '18 at 0:03

Another example from Euclid (in the proof of Proposition 20, Book IX):

Given a finite list of primes $p_1,p_2,\cdots,p_n$, there is a prime not included in the list.

Construction: Let $N=p_1 p_2 \cdots p_n +1$. Let $p$ be the smallest (to make the construction unique, Euclid didn't specify this) prime factor of $N$. Then $p$ is not equal to any of the primes $p_1,p_2,\cdots,p_n$.

There are infinitely many other solutions to the problem of finding such a prime.

• This one is prone to misinterpretation. Many students think that $p_1$_2\dots p_n+1$is prime. – Benoît Kloeckner Oct 24 '17 at 12:36 It is obvious that the algorithm given in the accepted answer (in the Mathematics Stack Exchange Site) to the question “Divide a plane with 2n points into two equal halves” (at: https://math.stackexchange.com/questions/3083344/divide-a-plane-with-2n-points-into-two-equal-halves/3083372#comment8100957_3083372) can be slightly modified to fit the situation you ask about. I might think in any diofantine equation as the one you propose. Also a lot of trigonometric equations. Something like$\sin\theta=\frac{1}{2}\$.

• Your answer appears to give example when there are several solutions. However, you do not indicate any unique procedure that leads to a non-unique solution. For the second example, one could say "applying the inverse sin function" (one might imagine, pressing the button on the calculator) is such a procedure. – quid Oct 22 '17 at 20:20
• Sorry if I wasn'y precise... But something around what you said is what I was thinking. Even more complex trigonometric equations use almost the same procedure every time. Take a quadratic trigonometric equation. A student would factor, then make every factor equal to 0, apply inverse function, then give the solution using the calculator usually avoinding given all the solutions. – Grouper Oct 22 '17 at 20:35
• If you like you can still add more details to the post by an edit. – quid Oct 22 '17 at 20:42