Fermat Little Theorem

part 1

Mengatakan bahwa jika \(p\) bil.prima, maka setiap \(\alpha\), berlaku \(\alpha^p - \alpha\) adalah bilangan bulat kelipatan \(p\)

a = 2
p = 3

a^p - a = 6

6 adalah kelipatan 3

\(\alpha^p \equiv \alpha \ (\bmod p)\)

part 2

jika \(\alpha\) tidak dapat dibagi \(p\), maka berlaku \(\alpha^{p-1} - 1\) adalah bilangan bulat kelipatan \(p\)

\(\alpha^{p-1} \equiv 1 \ (\bmod p)\)

Fermat's Factorization Method

\(N = a^2 - b^2\)

Warning

belum selesai

Generalisasi

Euler's Theorem

untuk setiap modulus \(n\) dan setiap bilangan bulat \(\alpha\) coprime dengan \(n\)

\(\alpha^{φ(n)} \equiv 1 \ (\bmod n)\)

juga berlaku jika \(x \equiv y \ (\bmod φ(n))\) untuk setiap bil.bulat \(x\) & \(y\), menyebabkan

\(\alpha^x \equiv \alpha^y \ (\bmod n)\)

Sumber

---

1. https://en.wikipedia.org/wiki/Fermat%27s_little_theorem ↩

2. https://en.wikipedia.org/wiki/Fermat's_factorization_method ↩