## infinitely many primes 1 mod p

For students of class 11-12 (age 16+)
nayel
Posts: 268
Joined: Tue Dec 07, 2010 7:38 pm
Location: Dhaka, Bangladesh or Cambridge, UK

### infinitely many primes 1 mod p

Here is a sequence of steps through which you can find infinitely many primes congruent to $1\bmod p$ for any prime $p$. (Of course, without having to use Dirichlet's theorem!)

A. Let $a>1$ be an integer.
B. Let $N=a^p-1$.
C. What is the order of $a\bmod N$?
D. This order must divide $\phi(N)$, where $\phi$ is Euler's totient function.
E. Consider the prime factorisation of $N$ to write down $\phi(N)$. Use D to show that there exists a prime $\equiv 1\bmod p$.
F. Can you make some clever choices for $a$ to find infinitely many such primes?
"Everything should be made as simple as possible, but not simpler." - Albert Einstein

Masum
Posts: 592
Joined: Tue Dec 07, 2010 1:12 pm

### Re: infinitely many primes 1 mod p

Nice. In a similar technique, I tried very hard to find some sort condition or special choices to force $\varphi(p)$ is a square. But still no luck. Must be. Otherwise I would already have solved $p=n^2+1$ problem.
One one thing is neutral in the universe, that is $0$.

asif e elahi
Posts: 183
Joined: Mon Aug 05, 2013 12:36 pm

### Re: infinitely many primes 1 mod p

nayel wrote:Here is a sequence of steps through which you can find infinitely many primes congruent to $1\bmod p$ for any prime $p$. (Of course, without having to use Dirichlet's theorem!)

A. Let $a>1$ be an integer.
B. Let $N=a^p-1$.
C. What is the order of $a\bmod N$?
D. This order must divide $\phi(N)$, where $\phi$ is Euler's totient function.
E. Consider the prime factorisation of $N$ to write down $\phi(N)$. Use D to show that there exists a prime $\equiv 1\bmod p$.
F. Can you make some clever choices for $a$ to find infinitely many such primes?
We prove that $p^{p^{k}}-1$ always has a prime divisor that is congruent to 1$mod p^{k}$.We assume the contrary .Let q be a prime divisor of it.Then $p^{p^{k}}\equiv1(mod q)$.Again by Fermat's theorem
$p^{q-1}\equiv 1(mod q)$.So $p^{gcd(p^{k},q-1)}\equiv 1(mod q)$.$gcd(p^{k},q-1)$=$p^{m}$ for some m.By our assumption ,$m\leq k-1$ or $q\mid p^{p^{m}}-1\mid p^{p^{k-1}}-1$.So all the prime divisors $p^{p^{k}}-1$ are divisors of $p^{p^{k-1}}-1$.But $p^{p^{k}}-1=(p^{p^{k-1}})^{p}=p^{p^{k}}-1)X$.here $gcd(p^{p^{k-1}}-1,X)=gcd(p^{p^{k-1}}-1,p)=1$.So $p^{p^{k}}-1$ has a prime divisor that dos'nt divide $p^{p^{k}}-1$.So our assumption was wrong.So $p^{p^{k}}-1$ always has a prime divisor that is congruent to 1$(mod p^{k})$.
We proved that,for all k,there are at least one prime q that is congruent to 1 $(mod p^{k})$.So there are infinite primes congruent to 1(mod p).