This is exercise 1.C.7 in Isaacs, Finite Group Theory. I have a solution, but I am suspicious that there is something wrong with it, because I do not fully use one of the hypotheses.
Let $G$ be a finite group in which every maximal subgroup has prime index, and let $p$ be the largest prime divisor of $|G|$. Show that a Sylow $p$-subgroup is normal. Hint: Otherwise, let $M$ be a maximal subgroup of $G$ containing $N_G(P)$, where $P \in Syl_p(G)$. Compare $n_P(M)$ and $n_P(G)$.
I argue as suggested in the hint. Suppose that $P \in Syl_p(G)$ and $P$ is not normal. Then $N_G(P)$ is a proper subgroup of $G$, so it is contained in some maximal subgroup $M$. This gives us the containments $P \leq N_G(P) \leq M < G$. Note also that $P \in Syl_p(M)$.
Since $|G:M|$ is prime and is not equal to $p$ (otherwise $|G:P|$ would be divisible by $p$), we have $|G:M| = q < p$ for some prime $q$.
Now $n_p(G) = |G:N_G(P)|$ and $n_p(M) = |M:N_M(P)|$. But $N_M(P) = N_G(P) \cap M = N_G(P)$ since $N_G(P) \leq M$. Therefore, $n_p(M) = |M:N_G(P)|$.
Summarizing, we have $n_p(G) = |G:N_G(P)| = |G:M|\,|M:N_G(P)| = q\,n_p(M)$. Taking this equation mod $p$ gives us $1 \equiv q$ mod $p$, since by Sylow's theorem both $n_p(G)$ and $n_p(M)$ are congruent to $1$ mod $p$. But $1 < q < p$, so we have a contradiction, and therefore $P$ must be normal after all.
My concern is that I don't seem to require that $q$ is prime, only that it is any integer satisfying $1 < q < p$. So, it would seem that the hypothesis "every maximal subgroup has prime index" could be replaced with "every maximal subgroup has index no larger than $p$". But Isaacs is generally very economical with his hypotheses, so I suspect that there is a problem with my proof. Also, this answer seems much more brief/straightforward than usual for this book.
If $P$ is not normal, then the contradiction you obtained is correct.
Note that he says $p$ is largest prime divisor of $|G|$, and this with his another hypothesis implies that all maximal subgroups have index $\leq p$. Your remark on hypothesis is correct, and so far, I didn't find any example where your weaker hypothesis fails the theorem.