The problem I am trying to solve is as follows:
Take a positive integer $N$. Give the function $f$, such that $f(N)$ generates the sequence of all fractions $\frac{k}{N}$ where $(0 \le k \le N)$ such that $\frac{k}{N}$ can be simplified ($k$ and $N$ are not co-prime*)
*This might actually not be sufficient to say (since 0 is co-prime to 1 for example), so below the definition I came up with, that includes 0 and N itself.
Fractions where the numerator and denominator share some factor.
a.k.a some fraction $\frac{i}{j}$ can be found such that $\frac{i}{j} = \frac{k}{N}$ where $\frac{i}{j}$ itself can't be simplified further or an integer $I$ can be found such that $I = \frac{k}{N}$.
An example would be:
Let $N = 12$
Now $f(12) = \{\frac{0}{12} , \frac{2}{12} ,\frac{3}{12} ,\frac{4}{12} ,\frac{6}{12} ,\frac{8}{12} ,\frac{9}{12} ,\frac{10}{12} ,\frac{12}{12} \}$
Which when simplified would become: $f(12) = \{0, \frac{1}{6} ,\frac{1}{4} ,\frac{1}{3} ,\frac{1}{2} ,\frac{2}{3} ,\frac{3}{4} ,\frac{5}{6} ,1 \}$
My related questions are:
- What is this sequence called?
- How would one name the sequence of all $GCM(k, N)$ (e.g. $\{0,2,3,4,6,8,9,10,12\}$)
- What would the function to generate this sequence look like?
Research I have already performed:
- All factors of $N$ form a subset of the numerators namely up to $\frac{N}{2}$, any numbers between $\frac{N}{2}$ and $N$ are therefore not included.
- All prime numbers generate the sequence $\{0, 1\}$ as they have no factors or numbers with which they share factors.
- I concluded I wanted a sequence of numbers for which the numerator and denominator aren't co-prime , but including $\frac{0}{N}$ and $\frac{N}{N}$
Best Answer
$\frac k N$ can be simplified if and only if $\gcd(k,N)>1$, i.e. if $k$ and $N$ share a common factor. So basically you just want to find all $k\in\{0,\ldots,N\}$ such that $\gcd(k,N)>1$. Probably the easiest way would be this:
There must be some prime number that divides both $p$ and $N$. So find all the prime divisors $p_1, \ldots,p_m$ of $N$, and take all multiples of all the $p_i$'s (up to $N$). That gives all $k$. We will find the some values multiple times though.
Example: $12=2^2\cdot3$. So we take all multiples of $2$ and $3$: $\{0,2,4,6,8,10,12\}$, $\{0,3,6,9,12\}$. We take the union of these, giving $$ k\in\{0,2,3,4,6,8,9,10,12\} $$
Using the formula for Euler's totient function, we have a nice expression for the number of values: $$ \#f(N) = N+1-\varphi(N) = N+1-N\prod_{p|N}(1-1/p) = 1+N\left(1-\prod_{p|N}(1-1/p)\right) $$ where the product is taken over the prime divisors of $N$. We can test it for $N=12$: $$ 1+12\left(1-\prod_{p|12}(1-1/p)\right) = 1+12\left(1-\left(1-\frac12\right)\left(1-\frac13\right)\right) = 9 $$
By the way, I am not sure your sets really have speciel names (other than just describing them in some way or other), since we tend to study the numbers that are coprime to $N$. I could be wrong about that. We could call them the zero-divisors modulo $N$, but that would make more sense in another context.
EDIT: We can compare your $f$ to Farey sequences like so: $$ \mathrm{Farey}(N) = \{\text{reduced fractions } \frac ab\in[0,1] \text{ where }b\le N\} $$ $$ f(N) = \{\text{reduced fractions } \frac ab\in[0,1] \text{ where } b\mid N, b\ne N\} $$ Let's find $f(12)$ again with that mindset: First find all proper divisors of $12$: $\{1,2,3,4,6\}$. Then find all irreducible fractions between $0$ an $1$ with these denominators: $$ \left\{\frac01,\frac11\right\}\cup \left\{\frac12\right\}\cup \left\{\frac13,\frac23\right\}\cup \left\{\frac14,\frac34\right\}\cup \left\{\frac16,\frac56\right\} = \left\{0,\frac16,\frac14,\frac13,\frac12,\frac23,\frac34,\frac56,1\right\} $$ Alternatively, you can take all fractions with $\{1,2,3,4,6\}$ as denominators and then reduce them. Then you will find the same reduced fractions multiple times.
We can also use the Farey sequences if we want. If $d$ is the largest proper divisor of $N$, then we can generate the Farey sequence of order $d$ using the algorithm on wikipedia for example. Then we remove all fractions with a denominator that does not divide $N$. For $N=12$ we would find $\mathrm{Farey}(6)$ and remove the terms with denominator $5$.