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?

## infinitely many primes 1 mod p

### infinitely many primes 1 mod p

"Everything should be made as simple as possible, but not simpler." - Albert Einstein

### 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**Location:**Sylhet,Bangladesh

### Re: infinitely many primes 1 mod p

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 theoremnayel 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?

$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).