Chapter 06 - Special Congruences.sagews

Chapter 6 - Special Congruences

%md
#### Introductory Example

Introductory Example

table([(k,3^k,mod(3^k,10)) for k in [1..8]],  header_row=["k","3^k","ones digit of 3^k"], frame="true")

+---+------+-------------------+ | k | 3^k | ones digit of 3^k | +===+======+===================+ | 1 | 3 | 3 | +---+------+-------------------+ | 2 | 9 | 9 | +---+------+-------------------+ | 3 | 27 | 7 | +---+------+-------------------+ | 4 | 81 | 1 | +---+------+-------------------+ | 5 | 243 | 3 | +---+------+-------------------+ | 6 | 729 | 9 | +---+------+-------------------+ | 7 | 2187 | 7 | +---+------+-------------------+ | 8 | 6561 | 1 | +---+------+-------------------+

%md
#### Example 6.5 ####

Example 6.5

powers=[3]
for k in [1..7]:
    powers.append(mod((powers[k-1])^2,221))
table([(2^k, powers[k]) for k in [0..7]], header_row=["t", "3^t mod 221"], frame=True)

+-----+-------------+ | t | 3^t mod 221 | +=====+=============+ | 1 | 3 | +-----+-------------+ | 2 | 9 | +-----+-------------+ | 4 | 81 | +-----+-------------+ | 8 | 152 | +-----+-------------+ | 16 | 120 | +-----+-------------+ | 32 | 35 | +-----+-------------+ | 64 | 120 | +-----+-------------+ | 128 | 35 | +-----+-------------+

Euler's phi function

We verify the calculation in Example 6.15 with the built-in Euler phi function.

euler_phi(561)

320