Eulerov záujem o teóriu čísel možno pripísať vplyvu Christiana Goldbacha, jeho priateľa z Petrohradskej akadémie. Mnohé z Eulerových raných prác v teórií čísel bolo založených na prácach [[Pierre de Fermat|Pierra Fermata]]. Euler niektoré Fermatove myšlienky rozvinul a niektoré jeho hypotézy vyvrátil.
Euler prepojil podstatu rozmiestnenia prvočísel s myšlienkami vz analýzeanalýzy. Dokázal, že súčet recipročných čísel k prvočíslam diverguje. Zároveň objavil vzťah medzi Riemannovou zeta funkciou a prvočíslami; ten je známy ako Eulerov súčinový vzorec pre Riemannovu zeta funkciu.
Euler dokázal Newtonove rovnosti (známe tiež ako Newtonove-Girardove vzorce), [[Malá Fermatova veta|Malú Fermatovu vetu]], Fermatovu vetu o súčte dvoch štvorcov a prispel k Lagrangovej vete o štyroch štvorcoch. Zaviedol aj funkciu φ(n), ktorá označuje počet prirodzených čísel menších ako číslo n, ktoré sú nesúdeliteľné s číslom n. Využitím vlastností tejto funkcie zovšeobecnil Malú Fermatovu vetu na vetu, ktorá je známa ako Eulerova veta. Výrazne prispel k teórii [[dokonalé číslo|dokonalých čísel]], ktoráktoré fascinovalafascinovali matematikov od čias [[Euklides|Euklida]]. Euler sa priblížil aj k prvočíselnej vete a predpokladal zákon reciprocity kvadratických zvyškov. Tieto dva fakty sú považované za základné vety teórie čísel a jeho myšlienky vydláždili cestu pre prácu [[Carl Friedrich Gauss|Carla Friedricha Gaussa]].
V roku 1772 Euler dokázal, že 2<sup>31</sup> − 1 = 2 147 483 647 je [[Mersennovo prvočíslo]]. Až do roku 1867 ostalobolo najväčším známym prvočíslom.
