Suppose that $p$ is a prime number.
Find all natural numbers $n$ such that $p|\varphi(n)$ and for all $a$ such that $(a,n)=1$ we have
\[ n|a^{\frac{\varphi(n)}{p}}-1 \]
1. **Given Conditions and Euler's Totient Function**:
   We are given that \( p \) is a prime number and we need to find all natural numbers \( n \) such that \( p \mid \varphi(n) \) and for all \( a \) such that \( (a, n) = 1 \), we have:
   \[
   n \mid a^{\frac{\varphi(n)}{p}} - 1
   \]
   Here, \(\varphi(n)\) is Euler's totient function, which counts the number of integers up to \( n \) that are coprime to \( n \).

2. **Prime Divisors and Totient Function**:
   For \( p \mid \varphi(n) \), \( n \) must have a prime divisor \( q \equiv 1 \pmod{p} \) or \( p^2 \mid n \). This is because \(\varphi(n)\) is a product of terms of the form \( p_i^{v_i-1}(p_i-1) \) for each prime \( p_i \) dividing \( n \).

3. **Order of Elements Modulo \( n \)**:
   Let \( c(n) \) be the highest order of any \( a \) coprime to \( n \) modulo \( n \). The order of \( a \) modulo \( n \) is the smallest positive integer \( d \) such that \( a^d \equiv 1 \pmod{n} \). By the properties of primitive roots modulo \( p^s \) for odd primes \( p \), we have:
   \[
   c(p^s) = \varphi(p^s)
   \]
   Additionally, for powers of 2:
   \[
   c(2) = 1, \quad c(4) = 2, \quad c(2^{k+2}) = 2^k \text{ for } k \geq 1
   \]
   For composite \( n \), we have:
   \[
   c(ab) = \mathrm{lcm}(c(a), c(b))
   \]

4. **Condition on \( c(n) \)**:
   We need \( c(n) \cdot p \mid \varphi(n) \). Let \( n = \prod p_i^{v_i} \) be the prime factorization of \( n \). This condition translates to:
   \[
   p \cdot \mathrm{lcm}_i (\varphi(p_i^{v_i})) \mid \prod \varphi(p_i^{v_i})
   \]
   This implies that we must lose some factor \( p \) in the \(\mathrm{lcm}\), which happens if and only if \( p \mid \varphi(p_s^{v_s}) \) and \( \varphi(p_t^{v_t}) \) for different \( s, t \). This is equivalent to having two different primes \( q_1, q_2 \equiv 1 \pmod{p} \) dividing \( n \) or at least one such prime together with \( p^2 \mid n \).

5. **Conclusion**:
   Therefore, the natural numbers \( n \) that satisfy the given conditions are those that have at least two distinct prime factors \( q_1, q_2 \equiv 1 \pmod{p} \) or one such prime factor and \( p^2 \mid n \).

The final answer is \( \boxed{ n } \) must have at least two distinct prime factors \( q_1, q_2 \equiv 1 \pmod{p} \) or one such prime factor and \( p^2 \mid n \).