# Fundamental period of a discrete-time signal

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.

• I added some math formatting to make it easier to read your question. But I also rearranged the first formula, putting n inside the exponential function, because I think this is the correct form for a complex exponential. Please revert if I changed the meaning of your question. Apr 5 '13 at 2:21

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.