# Fundamental Period of sequence modulo N

Let $T$ denote the smallest exponent such that $b^T \equiv 1 \pmod{N}$, then we call $T$ as fundamental period of the sequence satisfying the equation.

As an example for $b=2, N=2731$ we have $T=26$ since $T$ is the smallest number of the following sequence:

$${26,52,78,104,...}$$

It's obvious that $26$ is made of factors of $N-1$, here $\{2,13\}$. Assuming that we know all factors of $N-1$ even if $N$ is very large, without calculating the modular exponentiation for all $t$ up to $N$:

1. How we can know the existence of any $T$ less than $N$?
2. Is there any composite number having a $T$ less than N?
3. If there exist one, then how we can find it among the divisors of $N-1$?
-
For composite $N$, most of the time it will not be among divisors of $N-1$. Example, $N=15$, $b=2$. Are you assuming, without saying so, that $N$ s prime? Your example is. – André Nicolas Dec 11 '12 at 18:57
@AndréNicolas, your'true about composites.I'm looking to reduce the exponent for primility test. If I know $N$ is prime, then $N-1$ is an obvious member of the sequence – Mohsen Afshin Dec 11 '12 at 19:13
But as you know, even if $a^{N-1}\equiv 1 \pmod{N}$ for all $a$ relatively prime to $N$, it does not follow that $N$ is prime. – André Nicolas Dec 11 '12 at 19:17
I know that it becomes a PRP only, but it is the first step in any deterministic test. – Mohsen Afshin Dec 11 '12 at 19:26

I think you are asking, how do we know there is a positive integer $T$ less than $N$ such that $b^T\equiv1\pmod N$. The answer is, we don't --- if $\gcd(b,N)\gt1$ then there is no such $T$. But if we know $\gcd(b,N)=1$, then consider the numbers $$b,b^2,b^3,\dots,b^N$$ all reduced modulo $N$. There are $N$ numbers in that list, and they are all between $1$ and $N-1$, inclusive, so by the pigeonhole principle, two of them must be equal. If $1\le r\lt s\le N$ and $b^s\equiv b^r\pmod N$ then $b^{s-r}\equiv1\pmod N$ and $1\le s-r\lt N$. So, you can take $T=s-r$.
In your question 2 it's not clear whether you want $b$ to be composite, or $N$, but, either way, we have just proved you can take $T\lt N$.
And as pointed out in the comments, if $N$ is composite, there is no reason to think $T$ will be a divisor of $N-1$.
thanks for answer. As I told in the question I want to obtain $T$, without calculating the modular exponentiation for all $T$ up to $N$. With calculation it is obvious that $2^{27} \equiv 2^1 \pmod{2731}$. So $T = 27-1 = 26$ – Mohsen Afshin Dec 13 '12 at 12:41
The only question you asked about obtaining $T$ was "how can we find it among the divisors of $N-1$," and as you have been told twice we can't since it may not be among the divisors of $N-1$. – Gerry Myerson Dec 14 '12 at 0:35
As I know, if there is any $T$ it should be among divisors of $N-1$. That is, in case of existence of such a $T$, it should be made from the prime factors of $N-1$ so $T$ is one of divisors of $N-1$. – Mohsen Afshin Dec 14 '12 at 6:48
$T$ must be a divisor of $N-1$ if $N$ is prime, a condition which is mentioned nowhere in the body of your question and nowhere in your comments on my answer. If you mean for $N$ to be a prime, you should say so (and consider using $p$ instead of $N$). So: if $N$ is prime, and if you know the factorization of $N-1$, then you also know all the divisors $d$ of $N-1$, and you only have to calculate $b^d$ for such $d$. And you can calculate $b^d$ without first calculating $b^2,b^3,b^4,\dots$. Do you know how to do that? or is that what you are asking about? – Gerry Myerson Dec 14 '12 at 12:04
I assume that $N$ or $p$ is prime and I know full factorization of $N-1$. And I know all divisors of $N-1$. How do I know which divisor is $T$ (fundamental period)?. The real problem is this. – Mohsen Afshin Dec 14 '12 at 12:33