A Condition on Prime Numbers

Fermat's little theorem states that if p is a prime number, then for any integer a, the number $a^{p} - a$ is an integer multiple of p. In the notation of modular arithmetic, this is expressed as $a^{p}\equiv a \pmod p$ . Considering the question , $29^{p}\equiv -1 \pmod p$ . But as, $29^{p}\equiv 29 \pmod p$ . So we get , $30\equiv 0 \pmod p$ . Finally, $p=2,3,5$ ,i.e number of such primes is $3$

According to Fermat's Little Theorem, a^p==a(mod p) whenever a is an integer and p is a prime.

So, 29^p==29(mod p)

But according to the condition, 29^p==-1(mod p)

So, -1==29(mod p) Or, 30==0(mod p)

In other words, p must divide 30. The primes that divide 30 are 2, 3, and 5. So the answer is 3.

Note:- Fermat's Little Theorem can be proved this way. If p divides a, a^p-a is obviously a multiple of p, so we are done. If p does not divide a, g.c.d(a, p)= 1. According to Euler's Theorem a^phi(p)==1(mod p) Or, a^(p-1)==1(mod p) Or a^p==a(mod p)

General form we need to know for this problem is:

$n^p$ = $n$ (mod $p$ ) where $n$ is natural number and $p$ is prime number

from that form we can write: $n^p + 1$ = $n+1$ (mod $p$ ) in the problem we know that $n$ = 29 so $29^p + 1$ = 30 ( mod $p$ ) = 0 ( mod $p$ ) because $29^p + 1$ must be divisible by $p$

now we only need to find the prime factors of 30 which are 2,3 and 5 so there are 3 prime numbers fulfilling the requirements.

29^p + 1 = kp 29^p + 1 = 0 mod p 29^(p-1) * 29 = 1 mod p 29 + 1 = 0 mod p 30 = 0 mod p

from this, possible values of p are 2, 3, and 5.

by fermats theorem 29^p is congruent to 29 modulo p hence we are left with 30 which has to be divisible by prime p and hence it may take on values 2,3 and 5 hence total 3 possible prime numbers

a^p \equiv a \pmod {p}. so, 29^p \equiv 29\pmod {p}. so, 29^p + 1 \equiv (29 + 1) = 30\pmod {p}. so, p must divide 30. But, 30 = 2 3 5. so, there are 3 prime no.s for which these conditions are satisfied. so, 2,3,5 are the primes.

by fermat's little theorem,

$29^p + 1 \equiv 30 (mod p)$

If $30 \equiv 0 (mod p)$ , then p = 2, 3, 5.

Applying Fermat Little Theorem, we obtain $29^p + 1 \mod p \equiv 29 + 1 \mod p \equiv 30 \mod p$ . On the other side, $29^p+1$ is a multiple of $p$ . Hence, $29^p+1 \mod p \equiv 0$ . Combining these yields $30 \mod p \equiv 0$ , which means that $p$ must be a divisor of 30. So, there are 3 prime numbers $p$ satisfying the problem (2, 3, and 5).

$p \neq 29$ because $29^{29}+1\equiv 1 \pmod{29}$ . Then by Fermat's Little Theorem, $29^p+1\equiv 30 \pmod{p} \Rightarrow 30 \equiv 0 \pmod{p} \Rightarrow p|30$ . So the only possible values of $p$ are $2,3,5$ . It is trivial to check this solutions are valid. The answer is therefore $3$ .

From Fermat's Little Theorem we get $29^p \equiv 29(\pmod p)$ So $29^p+1 \equiv 30(\pmod p)$ Hence $p|30$ . So all possible values of p are 2,3,5. So there are 3 values.

All congruences are modulo p.

Here we should find all primes $p$ such that

$29^p + 1 \equiv 0$

From Euler's theorem we know that for each prime $p \neq 29$

$29^p \equiv 29$

And thus,

$29 + 1 \equiv 0$

This means that p can only be a divisor of 30. What if $p = 29$ ? We can easily conclude that $p = 29$ is not a solution, because $29^{29} + 1 \equiv 1$ . Since 30 has 3 unique prime divisors (2,3,5), the solution is 3.

Let $p$ be a prime and $a$ be a positive integer co-prime to $p$ . Then according to Fermat's Theorem : $a^{p-1} \equiv 1 \pmod{p}$ or $a^{p} \equiv a \pmod{p}$ or $a^p + 1 \equiv a+1 \pmod{p}$ . The question asks us to count number of primes which satisfy $29^p + 1 \equiv 0 \pmod{p}$ . But $29^p + 1 \equiv 30 \pmod{p} , p \neq 29$ . Combining these two, we have now that $30 \equiv 0 \pmod{p}$ . The only prime divisors of $30$ are $2, 3$ and $5$ . Each one of these is co-prime to $29$ . And for obvious reasons $29^{29} + 1 \equiv 0 \pmod{29}$ is a false statement. So three integers satisfy the given condition.

First of all, it is clear that $p=29$ does not satisfy the condition.

Assuming now that $p\not = 29$ , by Euler's Theorem we have $29^{p-1}\equiv 1\pmod{p}$ . (Note that we can do this because here 29 and $p$ are relatively prime.) Multiplying both sides of the congruence by 29 yields $29^p\equiv 29\pmod{p}$ . (We could also have gotten this by Fermat's Little Theorem, but it is a special case of Euler's Theorem, anyway.) Adding 1 to both sides gives $29^p+1\equiv 30\pmod{p}$ . Thus $29^p+1$ is a multiple of $p$ if and only if $30\equiv 0\pmod{p}$ . This occurs if and only $p$ divides 30. Finally since $30=2\cdot 3\cdot 5$ , there are only $\boxed{3}$ primes that satisfy the required condition.

Firstly, note that p=29 fails. Since 29 is a prime, by definition, $gcd({29},{p}) = 1$ for any prime p.

By Euler's Theorem, $29^{p-1} \equiv 1 \pmod{p}$ for all p. Then for the condition to be fulfilled, ie. $p \mid 29^{p} +1$ , $29^{p} +1 \equiv 29^{p-1} * 29 + 1 \equiv 29 + 1 \equiv 30 \pmod{p} \equiv 0 \pmod{p}$ .

So p divides 30. Thus only 3 values of p fulfil the equation: 2,3 and 5.

_ _Fermat Theorem __: Give $p$ a prime, and $x$ a coprime with $p$ , then $x^{p-1} \equiv 1 \mod p$ .

This way, we have that: $29^p+1 = 29^{p-1}\times 29 + 1 \equiv 1\times 29 +1 \equiv 30 \mod p$

And so $p|30$ therefore $p \in \{2,3,5\}$ .

ANSWER : 3

Since $p$ is prime, $\phi(p)=p-1$ . By Euler's Theorem, we have $29^{p-1} \equiv 1 \pmod{p}$ . Hence, $0 \equiv 29^p + 1 \equiv 29+1 \equiv 30 \pmod{p}$ . Thus, $p$ must divide $30$ , so $p=2, 3, 5$ are the only possibilities.

Hence there are $3$ prime numbers that satisfy the conditions.

Since 29^p +1 must be np So, p must be divisor of (29+1),it is 1,2,3,5,6,10,15,30 Conclution, answer with prime number is 2,3,5