Мабуть, Ейлер дізнався про роботи Ферма незабаром після свого приїзду до Петербурга в 1727 р. від Х. Гольдбаха (1690-1764) і зберіг інтерес до теорії чисел на все життя. Видатні колеги Ейлера віднеслися до його захоплення щонайменше без розуміння. Д. Бернуллi (1700 — 1782), який сам був не проти небагато позайматися арифметичними завданнями, в 1778 р. писав М. I. Фуссу (1755 — 1826), учневі Ейлера, з приводу арифметичних робіт його вчителя: «..чи не знаходите Ви, що простим числам надають, мабуть, дуже велику честь, марнуючи на них стільки сил, і чи не відображає це рафінований смак нашого століття?». Арифметичні проблеми Ейлер обговорює перш за все з Гольдбахом, математиком дуже оригінальним, але все таки не відносився до найбільших сучасників Ейлера, таким, як Ж. Р. Даламбер (1717 - 1783) або А.К. Клеро (1713-1765).

Положення стало іншим лише до кінця життя Ейлера, коли завдяки його роботам відношення до теорії чисел стало мінятися і він мав можливість обговорювати ці проблеми з Лагранжем в листах 1772-73 рр.

Вже в 1729 р. Ейлер дізнався від Гольдбаха про твердження Ферма, що числа

(1)

є простими при всіх . У 1732 році він виявив, що це твердження невірне, а саме ділиться на . Спостереження Ейлера не було результатом перебору: безпосередньо шукати дільників у було нереалістичне навіть для такого віртуозного обчислювача, яким був Ейлер. Він спочатку виявляє, що дільники мають дуже спеціальний вигляд (якщо вони існують): , а після цього виявити було неважко. Дивно, що перший захід Ейлера на доказ тверджень Ферма вивів його на єдине помилкове твердження. На щастя, це не поколивало довіри і інтересу до арифметики Ферма.

Інший клас простих чисел у полі зору Ейлера — це прості числа Мерзенна

( — просте). Дільники повинні одночасно мати вигляд і . Користуючись цим, Ейлер довів простоту числа . З тих пір нових простих чисел Ферма виявлено не було, а рекорди в світі простих чисел Мерсенна постійно збільшуються (рекорд 1983 р.: ; сьогодні комп'ютери рахують прості числа Мерсенна з неймовірним числом знаків).

Відносно чисел Мерсенна Ейлер заповнив також пропуск, що залишався від Евкліда. Евклід знав, що якщо — просте число, то — довершене число (тобто число, рівне сумі своїх власних дільників). Ейлер довів, що кожне парне довершене число уявне у такому вигляді (невідомо до цих пір, чи існують непарні довершені числа). Ейлера цікавить, чи існують многочлени , які при всіх натуральних приймають прості значення. Він отримує негативну відповідь, але замічає, що значення многочлена прості при всіх .

Ейлер забезпечує доведенням «малу теорему Ферма», яка стверджує, що число , де — ціле, що не ділиться на , а — просте, ділиться на але, не обмежившись цим, він знаходить і доводить її узагальнення для непростого дільника: якщо і взаємно прості, то ділиться на (тут — число натуральних чисел, взаємно простих з і менших . Виявивши, що функція натурального аргументу (її назвуть функцією Ейлера) володіє чудовими властивостями, він тим самим відкриває важливий розділ теорії чисел — теорію арифметичних функцій. Ейлер рухається дуже логічно. Він помічає, що для деяких число ділиться на при , а для деяких — ні. У останній ситуації називають первісним коренем по модулю . Експеримент переконує Ейлера, що первісний корінь існує для всіх простих , але довести цього він не зміг (доказ знайшли пізніше Лежандр і Гаус). Ейлер умів доводити важкі теореми, але він умів і тверезо оцінювати свої можливості. Він ніколи не концентрував роздуми над одним важким завданням на роки, а наступав на математичні таємниці широким фронтом.

Ще одне твердження, сформульоване Ферма без доведення, привернуло увагу Ейлера. Йдеться про уявність квадратів у вигляді , де — просте число. При таких квадратів не буває (чому?), а при маємо . Ферма стверджував, що для всякого простого виду існує квадрат виду , а для таких квадратів не існує. У 1747 р. Ейлер після декількох безуспішних спроб доводить це твердження Ферма і продовжує рух в природному напрямі: для яких число може бути квадратом і, ширше, для яких при фіксованому число може бути квадратом? При гіпотеза полягає в тому, що квадрати такого вигляду існують при і не існують в решті випадків. Загальна гіпотеза: квадрати виду ( — просте) існують (як то кажуть, є квадратичним вирахуванням по модулю ) або не існують одночасно для всіх простих з арифметичної прогресії (). Це твердження пізніше отримало назву «Квадратичного закону взаємності». Далі Лагранж і Лежандр розглядали випадки різних поки 19-річний Гаус не знайшов повне доведення гіпотези Ейлера.

Наступне коло питань, успадковане вiд Ферма, — це рішення рівнянь в цілих числах. Найбільш знамените твердження Ферма — його «Велика теорема»: рівняння

при натуральному не має розв’язкiв в цілих додатних числах (при такі розв’язки існують і називаються піфагоровими трійками). У 1738 році Ейлер знаходить доведення «Великої теореми Ферма» для , але він відмовився від спроби довести теорему для великих , не