This is an ipython (jupyter) worksheet with code from the lecture notes for the course Permutation Puzzles: A Mathematical Perspective, by Jamie Mulholland
Coures webpage: http://www.sfu.ca/~jtmulhol/math302
Course notes booklet: http://www.sfu.ca/~jtmulhol/math302/notes/302notes.pdf
Python commands // and % are used to compute quotients and remainders respectively.
29//8
3
29%8
5
Greatest Common Divisor (gcd)
gcd(343,273)
7
The extended euclidean algorithm is used to write the gcd of two numbers as a linear combination of the two numbers. xgcd
is the command for the extended euclidean algorithm.
xgcd(343,273)
(7, 4, -5)
This means $7 = 4\cdot343+(-5)\cdot 273$.
is_prime
is the command to check if a number is prime, or not.
is_prime(3)
True
is_prime(6)
False
Every interger can be factored into a product of primes.
factor(4590872)
2^3 * 11 * 13 * 4013
For any positive integer $n$, $\phi(n)$ is the number of integers in $\{1,2,...,n\}$ which are relatively prime to $n$. In other words, $$\phi(n)=|\{m\in \mathbb{Z} \mid 1\le m \le n, \gcd(m,n)=1 \}|.$$
euler_phi(96)
32
To find the 32 numbers relatively prime to 96 we can do the following.
[n for n in range(1,97) if gcd(n,96)==1]
[1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43, 47, 49, 53, 55, 59, 61, 65, 67, 71, 73, 77, 79, 83, 85, 89, 91, 95]
Or we could use a fliter with a lambda function.
filter(lambda x: gcd(x,96)==1,range(1,97))
[1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43, 47, 49, 53, 55, 59, 61, 65, 67, 71, 73, 77, 79, 83, 85, 89, 91, 95]