Tricki

## Computational number theory front page

### Quick description

Number theory tells us many beautiful results, but it does not always do so explicitly. For example, if is a prime number, then the multiplicative group mod must be cyclic: that is, there must exist some such that mod but whenever . But this result is proved by a counting argument that gives no clue about how to find such an or how to establish that a given number has that property. Such questions are the domain of computational number theory. There are a number of beautiful tricks in the area that make it particularly well suited to being discussed in the Tricki.

### Prerequisites

Elementary number theory, and especially modular arithmetic.

### Links to articles

Some of the tricks, though clever, are quite simple to explain. As a result, some of the following articles are quite short.

To work out powers mod , use repeated squaring

To establish that is composite, show that Fermat's little theorem does not hold for

To find a factor of , find some such that

To factorize , find a non-trivial square root of mod

To find a rational with low denominator near a given real, use continued fractions