This question comes right out of the problems section of Oppenheim's Signals & Systems 2ed textbook. I don't understand the solution to the problem.
(problem #1.35)
If a discrete-time complex sinusoid is expressed by \$x[n] = \exp(jmn2\pi/N)\$ (m is any integer), prove that the fundamental frequency is N0 = N/gcd(N,m).
Solution: for a discrete-time signal to be periodic \$x[n]= x[n+N_0]\$.
Substituting n+N0 into n and expanding that expression means that \$m(2\pi/N)N_0 = 2\pi{}k\$,
where k is some (not any) integer. Rearranging we get the expression N0=N/(m/k).
somehow (m/k) = gcd(N,m).
I don't see it.
Best Answer
Let's write the book's solution out in more detail.
First, by definition, a discrete-time signal is periodic with period N0 if for all n, \$x[n+N_0] = x[n]\$.
So we're interested in cases where
\$\exp(j2\pi{}mn/N) = \exp(j2\pi{}m(n+N_0)/N)\$.
We know that the complex exponential, considered as a continuous function, repeats whenever it's argument advances by \$2\pi\$. So our equality holds whenever the phase difference between the arguments increases by some multiple of \$2\pi\$, that is whenever there is a k such that
\$2\pi{}mn/N + 2\pi{}k = 2\pi{}m(n+N_0)/N\$.
We can eliminate terms here to get
\$ mn/N + k = mn/N + mN_0/N\$
and further
\$ k = mN_0/N \$
So the period of our discrete time function is
\$N_0 = Nk/m\$
But N0 must be an integer, and we also want the smallest possible value of N0 to get the fundamental frequency. That means we want the smallest k that makes Nk/m an integer.
Lets write this out in terms of the prime factors of N and m:
\$N_0 = \dfrac{k \Pi_p n_p}{\Pi_q m_q} \$
For this to be an integer we need k to be made up of all the factors of m, except the ones that are held in common with N.
\$ k = \dfrac{\Pi_q m_q}{\Pi_{\mathrm{common\ factors}} m_q}\$
But the numerator here is just m, and the denominator here is just the gcd of N and m, so we have
\$ m / k = \gcd(N, m)\$
which is what we were trying to show.
TL;DR: It's to make it work out so that N0 is an integer.