#!/usr/bin/env python
# coding: utf-8

# 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 <br />
# Course notes booklet: http://www.sfu.ca/~jtmulhol/math302/notes/302notes.pdf

# ## Appendix B: Basic Properties of Integers

# ### B.1 Divisibility and the Euclidean Algorithm
# 
# Python commands // and % are used to compute quotients and remainders respectively.

# In[4]:


29//8


# In[5]:


29%8


# **Greatest Common Divisor** (gcd)

# In[7]:


gcd(343,273)


# 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.

# In[8]:


xgcd(343,273)


# This means $7 = 4\cdot343+(-5)\cdot 273$.

# ### B.2 Prime Numbers
# 
# `is_prime` is the command to check if a number is prime, or not.

# In[15]:


is_prime(3)


# In[16]:


is_prime(6)


# Every interger can be factored into a product of primes.

# In[20]:


factor(4590872)


# ### B.3 Euler's $\phi$-Function
# 
# 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 \}|.$$
# 
# 

# In[10]:


euler_phi(96)


# To find the 32 numbers relatively prime to 96 we can do the following.

# In[11]:


[n for n in range(1,97) if gcd(n,96)==1]


# Or we could use a fliter with a lambda function.

# In[14]:


filter(lambda x: gcd(x,96)==1,range(1,97))


# In[ ]:





# In[ ]: