前提知識
群論は絶対に必要です．群の作用についての知識が必要になることはほぼありませんが，有限Abel群の知識は要求されます．準同型定理はもちろん，有限生成Abel群の基本定理も求められる機会があります．
更に，剰余環の単数群 $(\mathbb{Z}/ n \mathbb{Z})^{\times}$ の構造定理が必要になる場面もあります．これはそのときに改めて学べば十分ですが．
離散最適化も必要と書いていますが，これは少々大げさな表現です．必要になるのは計算数論においてだけであり，しかも要求されるのは離散最適化全体ではなく「アルゴリズムとデータ構造」や「計算複雑性」についての基礎知識だけです．おそらく教科書のAppendixやイントロに書かれているはずなので，知らないままでも問題ありません．
ただし，計算を数学の対象として扱うという発想に馴染みがないようだと困ります．
また，微積分も学んだことがある方がよいでしょう．明示的に必要になるわけではありませんが，ある程度解析的な議論に慣れていないと本のペースについていけない可能性があります．さらに高校で習う程度の確率論も必要になります．
概要
Dedekind環論や複素解析などの大掛かりな道具を使っていない証明のことを，初等的な証明といいます．初等整数論とは，整数論のうち初等的に示せる部分のことです．
したがって「初等整数論」は分野名ではありません．つまり，固有の問題意識に付いた名前ではないわけです．予備知識が少なくても理解できる範囲に特に名前がついているだけです．
どこまでを初等的とするかは人によって異なりますが，筆者は有限Abel群論まではぎりぎり「初等的」と言って良い範囲だと思っています．
数論は主に次の３つの分野に分かれます．
暗号理論・計算数論
素数分布論・解析的整数論
不定方程式論・ディオファントス幾何
それぞれに初等的に示せる範囲があり，その部分が初等整数論と呼ばれます．
「代数的整数論は？」と思われるかもしれません．代数体やDedekind環，類数といった代数的な概念を導入してその性質を調べる分野です．Fermatの最終定理の証明を模索する中で生み出された分野で，その起源からして不定方程式論とかなり重複しますので，本稿では代数的整数論は代数学の一分野として扱うことにします．
数論のそれぞれの分野について初等的に示せる（したがって初等整数論に属する）定理を簡単に挙げていきます．
暗号理論・計算数論
素数判定アルゴリズムや，素因数分解アルゴリズムを設計する分野です．初等的な範囲では
ユークリッドの互助法
フェルマーの小定理とカーマイケル数
中国式剰余定理
RSA暗号（最初の公開鍵暗号．素因数分解の困難さに基づく）
あたりが鉄板でしょう．もう少し高度ですがギリギリ初等的に示せるものとして，
素数判定のAKSアルゴリズム（はじめて決定的多項式時間であることが証明された素数判定アルゴリズム）
ミラー・ラビン判定法（高い確率で素数であることを保証するか，あるいは合成数であると結論づけるアルゴリズム．）
などがあります．有限Abel群論や初歩的な環論が見事に応用されるので，代数学の授業をとっているひとは勉強すると楽しいと思います．
素数分布論・解析的整数論
素数がどのように分布しているのかを考える分野です．解析的手法を使いがちなので普通は解析的整数論と呼ばれます．(本稿では問題意識をわかりやすくするために素数分布論と呼んでいます)
初等的な範囲で示せるものとしてとりあえず知っておくべきなのは
素数が無限にあること
４で割って $k$ 余る素数がいずれも無限にあること （$k=1,3$）（これはディリクレの算術級数定理の特別な場合）
あたり．もう少し巧妙な議論をすれば，
チェビシェフの定理（素数定理の少し弱いバージョン．素数の個数の増加のオーダーが $x / \log x$ に一致すると主張する）
素数の逆数和の増加オーダーが $\log \log x$ であること
Bertrand の仮説（ある正の整数とその２倍の間に，素数が必ずある）
も証明できます．複素解析を使わなくてもかなり非自明なことが示せるのは，驚きではないでしょうか？
不定方程式論・ディオファントス幾何
多項式で定義される図形の，整数点と有理点について考察する分野です．
有名なFermatの最終定理はこの分野に属します．
考察している多項式の次数が２以下のときは不定方程式論と呼ぶことが多い気がします．次数が３のときには楕円曲線論と呼ばれ，さらに一般化した時にディオファントス幾何と呼ばれるイメージ．（間違ってたらごめんなさい）
数論幾何もその延長上にありますが，数論幾何と言った場合はスキーム論を前提としており，まだこの時点では概観を説明することさえできません．（そもそも私には数論幾何のことは何もわかりません）
初等的に示せる範囲で重要なのは，ダントツで
算術の基本定理（すべての整数は素数の積に一意に表せる）
平方剰余の相互法則（ある数が平方剰余であるかどうかを高速で計算できると主張する）
フェルマーの２平方和定理．（素数 $p$ を４で割った余りが１ならば $p = a^ 2 + b^ 2$ と表せる）
の３つでしょう．手間こそかかるものの
Fermatの最終定理の $n=4$ の場合
ラグランジュの４平方和定理
あたりも初等的に示すことができます．
文献
Shoup『A Computational Introduction to Number Theory and Algebra』
著者により無償で公開されている教科書です．ただ単に安いだけでなく，中身も素晴らしいものですよ．RSA暗号からAKSアルゴリズム（素数判定問題に対する決定的多項式時間アルゴリズム）まで，幅広い話題をカバーしています．
タイトル通り計算数論の話が充実しているのですが，実は素数分布論に関して初等的な範囲でのそこそこ詳しい記述もあって驚かされます．素数定理の証明こそされていないものの，それに近いことを主張するチェビシェフの定理の証明が載っています．アルゴリズムの計算時間を解析する際に関連するからなのですが，この本１冊で素数分布論まで勉強できて大変お得です．
更にこの本には self-contained であるという大きな長所があります．ミラーラビン法の解析や正当性の証明が見つからなくて困っていた私を，この本が助けてくれました．
Silverman『はじめての数論』
丸善出版から．AECの著者として有名な Silverman による有名な入門書．
2022年になって第4版の邦訳が登場しました．第3版の邦訳は洋書特有のよくわかんないノリが強調されていて手に取りづらかったのですが，第4版は教科書として使いやすい出来になっています．詳しくは次の比較記事を参照してください．．
暗号理論への応用が強調されていること，演習問題が工夫されていることが特色．事実の羅列でもなく，レールを綺麗に引きすぎて読者が自分で考えるのをやめてしまうような本でもなく，絶妙なバランスで「読者に自分で考えさせる」ことを高水準で実現しています．お勧めできる本．RSA暗号の説明ではこの本がいちばんわかりやすかったと思います．
ただしもちろん欠点もあります．
まず１つに，self-contained でないことが挙げられます．たとえば，ミラーラビン判定法が正しく動作することの証明が他書に譲られています．また，演習問題の中には（著者により注意されてはいますが）本書の内容だけでは解けないものが含まれています．
また２つめの欠点は，本書の後半部分の楕円曲線の話がかなり駆け足になってしまっていることです．この本だけを読んで理解するのは難しく，ほとんど蛇足になってしまっています．
しかし，全体としては依然として良い本だと思います．
Takloo-Bighash『A Pythagorean Introduction to Number Theory』
分野で言うと不定方程式論に近いです．Pythagorean Introduction とタイトルにある通り，ピタゴラスの定理を満たす数 $a^ 2 + b^ 2 = c^ 2$ について考察することから始めて，初等整数論を解説していこうという試みの本です．
アイデアとしては Cox の『Primes of the form $x^ 2 + n y^ 2 $』に近くて，単一の問題によって整数論の理論を動機づけようという発想であるようですね．Prefaceにある次の文章が著者の姿勢をよく表しています．
Mathematicians never develop theories in the abstract.
Despite the impression given by textbooks, mathematics is a messy subject, driven by concrete problems that are unruly. Takloo-Bighash『A Pythagorean Introduction to Number Theory』
こういう発想で書かれている本は好きです．
普通のテキストだと類数の有限性を示すところで唐突に導入される Minkowskiの凸体定理が，この本では平方和に関する文脈で自然に紹介されていて，その点も気に入っています．
次に学べる分野
整数論の世界は奥深く，ここから先に広大な世界が広がっています．
暗号理論を学べば，整数論がどのようにして暗号技術と関わっているのかがわかります．整数論で学んだ概念がどのように活用されるのか知れば，整数論に対する理解が深まるでしょう．
２次体の理論というのは，不定方程式論に属する分野です．有理数体 $\mathbb{Q}$ に２次多項式の根を付け加えて拡大したものを２次体というのですが，これを考察することは不定方程式を解くうえで重要なことです．さらに体論やGalois理論を学べば，前提知識としては十分です．
解析的整数論というのは，素数の分布を調べる分野です．使う道具が全く異なるので，初等整数論を知らなくても証明を読んで理解することはできます．初等整数論に加えてさらに複素解析またはFourier解析を学べば，ここに進むことができます．
