<jupyter_start><jupyter_text>Euler phi function $\phi(N)$ counts the number of integers in mod N that is coprime to N (i.e. having no common factor greater than 1)<jupyter_code>euler_phi(10) # [1, 3, 7, 9]<jupyter_output><empty_output><jupyter_text>Properties1. $\phi\left(p^{k}\right)=p^{k}-p^{k-1}=p^{k-1}\left(p-1\right)$ for any prime $p$1. $\phi\left(ab\right)=\phi\left(a\right)\phi\left(b\right)$ whenever $\gcd\left(a,b\right)=1$  Proof of (1)For a prime power $N=p^k$, all multiples of p has a common factor $p$ with $N$.The total number of coprimes can be counted as $$ N - \frac{N}{p}$$The above can be written as $p^k - p^{k-1}$  Idea of (2)We can represent each number from $0$ to $N-1$ by $(x,y)$For example, if $N=70=14\times 5$,we can arrange the 70 numbers in a grid by 5 rows and 14 columns, (and label from 0 to 4 for row, 0 to 13 for column)$(1,2)$ is there the 1st row 2 column, which represent the element $14(1)+(2) = 16$$(3,4)$ is the element $14(3) + 4 = 56$the last element is naturally $(4,13)$ which means $14(4) + 13 = 69$From this representaiton, we can see that at least half element in the 4th row has a common divisor $2$ with $70$  Elegant observationRecall that the pair $(x,y)$ is just the expression $14x + y$If we focus on the right index,$(\cdot, k)$ has a non-trivial common divisor with $70$ if $k$ has a non-trivial common divisor with $14$!!So, we can pick the columns that is coprime with $14$, which has $\phi(14)$.  Remaining caseIn each of the selected column $t$, we know that the numbers are of the form $14x + t$ and $\gcd(14x+t, 14)=\gcd(14, t)=1$i.e. every number in the selected colum is coprime with $14$.Therefore, if we are able to filter out the remaining numbers which share a common factor with 5, then we are done.How many are there?Exactly $\phi(5)$ !!Therefore, total number of coprimes is $\phi(14) \times \phi(5)$If we replace the above with $a$ and $b$, then we have the proof.<jupyter_code>euler_phi(70)
euler_phi(14) , euler_phi(5)<jupyter_output><empty_output><jupyter_text>Euler's theoremLet $a$ and $n$ be coprime, then $$a^{\phi(n)} \equiv 1 \pmod{n}$$Furthermore, if $m$ is the smallest power such that $$a^m \equiv 1 \pmod{n}$$then $m$ divides $\phi(n)$<jupyter_code>17^24 % 70
min([k for k in [1..24] if 17^k%70==1])
(1/7).n()
10^6 % 7
(1/13).n()
10^6 % 13<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.1521186440677966, 'fraction_numerical': 0.053389830508474574, 'mean_word_length': 4.675480769230769, 'pattern_counts': {'":': 0, '<': 13, '<?xml version=': 0, '>': 13, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '3', 'dir': 'jupyter-structured-clean-dedup', 'id': '477336', 'license': 'MIT', 'n_tokens_mistral': 936, 'n_tokens_neox': 845, 'n_words': 336, 'path': '20210417/5 - Euler functions.ipynb', 'repo_name': 'izayoi-ami/2021-hkage-sage-programming', 'size': '2360'}