# Chapter 2: Divisibility and Modular Arithmetic

## Index:

### 2.1: Prime Factorization of Positive Integers

Given a positive integer, this gives the prime factorization of the integer.  NOTE:  Large integers may take a great deal of time to factor.

Usage:

To obtain the prime factorization of an integer: Enter a positive integer and press enter.

Ex:
Positive Integer: 250

Top

### 2.2: Successive Prime Finder

Given a positive integer, this gives the next smallest prime.

Usage:

To obtain the next smallest prime after an integer: Enter a positive integer and press enter.

Ex:
Positive Integer: 250

Top

### 2.3: The Division Algorithm

Given a dividend a, and a divisor d, this performs the division algorithm gives the quotient q and the remainder r.

Usage:

To perform the division algorithm: Enter a positive dividend a, and a positive divisor d and press enter.

Ex:
Dividend: 243
Divisor: 17

Top

### 2.4: The Euclidean Algorithm

Given two positive integers, A and B, this gives their GCD.

Usage:

To determine the GCD of two posive integers: Enter a positive integer A, a positive integer B, and press enter.

Ex:
A:57881234
B:1212136

### 2.5: The Mod Function

Given an integer, B, and a modulus, M, this computes the remainder in the division of B by M

Usage:

To compute the remainder of an integer B (mod M): Enter two positive integers B and M and press enter.

Ex:
B: 6
M: 5

### 2.6: The Extended Euclidean Algorithm

Given two positive integers, A and B, output their gcd = D, and two integers X and Y such that AX+BYD

Usage:

To perform the extended Euclidean algorithm: Enter two positive integers, A and B, and press enter.

Ex:
A: 14
B: 235
Top

### 2.7: Finding Modular Inverses

Given an integer a, and a modulus m, output the inverse of a (mod m)

Usage:

To find a modular inverse: Enter two positive integers, a and m, and press enter.

Ex:

a: 16
m: 7

Top