Coprime Period

0,1,0,1,0,0,0,1,0,1period,0,1,0,1,0,0,0,1,0,1,0,\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 nn be a positive integer, and let the function fn: N{0,1}f_n:\ \mathbb N \to \{0,1\} be defined by fn(m)={0gcd(n,m)>11gcd(n,m)=1.f_n(m) = \begin{cases} 0 & \gcd(n,m) > 1 \\ 1 & \gcd(n,m) = 1. \end{cases} That is, fn(m)f_n(m) tells us whether mm is coprime to nn or not. If we write out the values of fn,f_n, we get a periodic (repeating) pattern. For instance, the list above gives the values of f10f_{10} starting at m=0m = 0; the pattern repeats itself with period 10.

Consider the function f1400f_{1400}. What is its period?


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

×

Problem Loading...

Note Loading...

Set Loading...