A Relatively Prime function¶
Consider the function of positive integers where for each positive integer \(n\), \(\phi(n)\) is equal to the number of integers between 0 and \(n\) are relatively prime (or coprime) to \(n\).
Relative primeness is an important concept in many areas of mathematics from number theory to linear algebra. Two positive integers are relatively prime, also known as coprime, if they have no divisors in common other than 1; i.e. their GCD (greatest common divisor) is 1.
In order to calculate the values of this function for a given \(n\), we will use the GCD. The GCD of any two positive integers \(a\) and \(b\) is the largest integer that divides both. One way to calculate the GCD is to use the Euclidean division algorithm.
Assume that \(a\geq b\). The algorithm works by first dividing \(b\) into \(a\) to get the quotient \(q_1\) and remainder \(r_1\) so that \(a = q_1\cdot b + r_1.\) If \(r_1 = 0\), then the GCD is \(b\). If not, then the algorithm continues by dividing \(r_1\) into \(b\) to obtain quotient \(q_2\) and remainder \(r_2\) such that \(b = q_2 \cdot r_1 + r_2.\) If \(r_2 = 0\), then the GCD is \(r_1\). If not, the algorithm continues in general by dividing \(r_j\) into \(r_{j-1}\) obtaining quotient \(q_{j+1}\) and remainder \(r_{j+1}\) such that \(r_{j-1} = q_{j+1} \cdot r_j + r_{j+1}.\) If \(r_{j+1} = 0\), then the GCD is \(r_j\). If not, continue.
The goal of this project is to investigate properties of \(\phi(n)\) graphically using Python, and algebraically.
Project¶
Write a Python function that will calculate the value of \(\phi(n)\) given a positive integer \(n\). Then use this function to graph Euler’s totient up to some \(N\), and make observations of any patterns you see in the graph. Next, hypothesize algebraic properties of \(\phi\) to explain any patterns you see, and then test your hypotheses using Python.
Note. I do not expect all your hypotheses to be correct. What I want to see is that you are not only thinking deeply about the patterns and trying to explain them, but also following through with your hypotheses by designed some simple Python experiments.
Values of \(\phi(n)\). The first 10 values of the function are given below.
n |
\(\phi(n)\) |
|---|---|
1 |
0 |
2 |
1 |
3 |
2 |
4 |
2 |
5 |
4 |
6 |
2 |
7 |
6 |
8 |
4 |
9 |
6 |
10 |
4 |