Primes
6. The right stuff New mathematics problems come in a wide range of difficulty. Some new questions are simple "exercises" and can be solved by applying wellknown theorems in a straightforward way. Solving such exercises begins to develop one's mathematical muscles. Other new questions are hard "exercise." They can be solved using known theorems in a clever way, or with persistence. Other questions reside in an area which requires the putting together of a variety of ideas leading to a solution. The solutions to such questions, which have interest to a reasonably large number of mathematicians, wind up being published in research journals to show other researchers new ideas, methods, and often new problems which grew out of the solution of the old ones. From time to time, interesting and important problems defy the best efforts of researchers for a sizable amount of time. Among the most famous of such problems was Fermat's Last Theorem, which eventually succumbed to the efforts of Andrew Wiles and Richard Taylor and those that set the stage for their work. This problem had gone unresolved for so long that it took great courage for Wiles to work on it for so long. When a problem is unresolved for a long time, anyone contemplating working on this problem knows that many other smart people have worked on it in the past and not been successful. This can often be intimidating since lots of very able mathematicians have often been attracted to longstanding problems and it does not push one's career along to work for a long time on a problem only not to succeed. (Thus, it is probably good advice to upandcoming mathematicians not to work on problems that have eluded solution for a long time until they have reached a phase in their careers where they have the "luxury" of failing.)
Another aspect of important discoveries is that the first work is rarely the last word in insight into solving a longstanding problem. Almost invariably ways to shorten and improve the original breakthrough are found. Such was the case for trying to find an algorithm which would show that it is possible to determine in polynomial time whether or not a given integer is prime.
Not only was their algorithm and the proof that it did what it was supposed to do correct, but given fairly standard number theory background, their work was relatively accessible. Agrawal, Kayal, and Saxena's work has set in motion a chain reaction whereby they and other number theorists have attempted to improve and explore the ramifications of their initial breakthrough.
The problem with this congruence is that it involves polynomials rather than numbers, and when n is a large integer these polynomials require lots of computation time to work with. The next idea was that perhaps one could get to work with polynomials of lower degree by dividing the congruence above by another polynomial and considering:
They showed that the above congruence held when n was prime and r and n are relatively prime to a. Their new algorithm grew from a successful investigation of what conditions on a and r allow one to conclude that when the congruence above holds, n must be prime. 
Welcome to the These web essays are designed for those who have already discovered the joys of mathematics as well as for those who may be uncomfortable with mathematics. Search Feature Column Feature Column at a glance 
Comments: Email Webmaster 
© Copyright
, American Mathematical Society


