Coprime Period

\[\large\underbrace{0,1,0,1,0,0,0,1,0,1}_{\text{period}}, 0,1,0,1,0,0,0,1,0,1,0,\dots\] Let \(n\) be a positive integer, and let the function \(f_n:\ \mathbb N \to \{0,1\}\) be defined by \[f_n(m) = \begin{cases} 0 & \gcd(n,m) > 1 \\ 1 & \gcd(n,m) = 1. \end{cases}\] That is, \(f_n(m)\) tells us whether \(m\) is coprime to \(n\) or not. If we write out the values of \(f_n,\) we get a periodic (repeating) pattern. For instance, the list above gives the values of \(f_{10}\) starting at \(m = 0\); the pattern repeats itself with period 10.

Consider the function \(f_{1400}\). What is its period?

\(\)
Note: The period is defined as the smallest possible value, that is, the least positive \(T\) such that \(f_n(m + T) = f_n(m)\) for all integers \(m\).

×

Problem Loading...

Note Loading...

Set Loading...