Finding the maximum value of p that satisfies this equation $3^p+5^p−1=q$ for $p,q \in \Bbb P$
I just don't understand how we can find the maximum value of p that allows p and q to be primes. So far, 3 seems to be the largest number that works here; although I can't prove that it is the largest one. This was a National Olympiad problem.
 A: Generally, these types of olympiad problems come down to 2 main methods. One is finding a factorization for a term that is suppsedly a prime (and then the solutions are "small variable cases" where the factorization produces a factor of $\pm1$). The other is trying to prove that the term that is suppsedly a prime is divisible by some fixed number (or one of a small set of numbers).
$$f(p)=3^p+5^p−1$$
does not easily allow a factorization, at least I couldn't find any.
That leaves the second approach. An experimental approach, which may not be possible in an Olympiad setting due to time and resource constraints, is to actually calculate the value of $f(p)$ for small $p$ like $2,3,5,7$ and then factor the resulting numbers. That can give you a conjecture about which number(s) $d$ are good candidates as potential divisors.
In this case, there are 2 indicators that $d=7$ might be a good candidate to consider as divisor. First, whatever $d$ you consider, the powers $3^p \pmod d$ and $5^p \pmod d$ will be purely periodic each. So there is a common smallest periodic length $l$ such that $3^a \equiv 3^{a+l} \pmod d$ and $5^a \equiv 5^{a+l} \pmod d$, in other words, the remainder of $f(n) \pmod d$ (taken for any positive integer $n$) will be periodic with period $l$.
Now, we don't know what $l$ is beforehand, but it is certain that some prime numbers $p \equiv 1 \pmod l$ will exist. For those primes $p$, we have
$$f(p) \equiv f(1) \equiv 7 \pmod d.$$
If we want to succedd in proving that $f(p)$ cannot be a prime, that only works for $d=7$.
The other indicator is that all primes $p>3$ are of the form $p=6k\pm1$. Knowing Fermat's Little Theorem, we know that $3^6 \equiv 1 \pmod 7$ and $5^6\equiv 1 \pmod 7$, which makes it easy to generally calculate $3^{6k\pm1}$ and $5^{6k\pm1}$.
So, this motivates considering $d=7$. If we do that, we see that for $p>3$ we have either
$$f(p)=3^{6k+1}+5^{6k+1}-1 \equiv 3\times (3^6)^k + 5\times (5^6)^k -1 \equiv 3\times 1^k + 5\times 1^k-1 \equiv 7 \equiv 0 \pmod 7$$ or
(using $6k-1=6(k-1)+5$)
$$f(p)=3^{6k-1}+5^{6k-1}-1 \equiv 3^5\times (3^6)^{k-1} + 5^5\times (5^6)^{k-1} -1 \equiv 3^5\times 1^{k-1} + 5^5\times 1^{k-1}-1 \equiv 5 +3 -1 \equiv 0 \pmod 7,$$
using step by step calculations to get $3^2 \pmod 7$ then $3^4 \pmod 7$ and finally $3^5 \pmod 7$, and the same for $5^5 \pmod 7$.
That means for every $p>3$, $f(p)$ is divisible by $7$, and since $f(p)>7$ in that case, it can't be a prime. That leaves $p=2,3$ to check, and as you noted, $p=3$ produces a prime $f(3)=27+125-1=151$, so $p=3$ is the answer to your problem.
