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. Commented Oct 23, 2017 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. Commented Sep 19, 2018 at 21:44
• A piece of advise: you say that your equation ($55x+32y=1$) has solution $(7, -12)$ and then you go to $(7+32t,−12−55t)$. Don't do that! First ask them what they think about $(-25, 43)$, and once they've realise there might be two solutions, you drop them $(39, -67)$. Only after that, you mention the general solution (with parameter $t$), rewriting $55x+32y=1$ as $55x+32y \pm 55 \cdot 32 \mp 55 \cdot 32=1$. Commented Dec 18, 2023 at 9:16
• @Dominique I was summarizing what I do, so I don't necessarily present the algebraic expression that gives all integral solutions at once. Actually, sometimes I present the graph of $55x+32y = 1$ and they can then see why there is a whole array of equally spaced integral solutions without dwelling on algebraic manipulations first.
– KCd
Commented Dec 18, 2023 at 19:21

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. Commented Oct 24, 2017 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. Commented Oct 24, 2017 at 19:20

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.

Giving examples is not the only thing I would do in this case.

I would also introduce new vocabulary. Having precise words helps when talking about precise concepts.

If each step of an algorithm can be executed in a unique way, then the algorithm is deterministic. This means that if two different people execute this algorithm, they will get the same result, even if they execute it on different days with different weathers and while feeling in different moods.

Yes, the output of the algorithm is unique. This does not imply that the solution to the problem is unique.

• @KCd Also, I didn't think about mentioning that when I wrote the answer, but given one mathematical problem (such as an equation) you can devise more than one algorithmic problem (for instance P0 = "Determine whether a solution exists"; P1 = "Find a solution" and P2 = "Find the set of all solutions"). Given an algorithmic problem you can devise more than one algorithm. An algorithm might be deterministic or not. And when you have an algorithm, you can write a "Proof of correctness" which is a mathematical proof that the algorithm really solves the algorithmic problem it's supposed to solve.
– Stef
Commented Dec 18, 2023 at 15:09

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
Commented Sep 19, 2018 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. Commented Oct 24, 2017 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
Commented Oct 22, 2017 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. Commented Oct 22, 2017 at 20:35
• If you like you can still add more details to the post by an edit.
– quid
Commented Oct 22, 2017 at 20:42