MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

Sure. $a\equiv b\pmod{\mathfrak{P}}$ just means $a-b\in\mathfrak{P}$. Taking norms to any subfield $K$ of $\mathbb{Q}(\zeta_n)$ (e.g., $\mathbb{Q}$ or $\mathbb{Q}(\zeta_m)$) gives you $N_{\mathbb{Q}(\zeta_n)/K}(a-b)\in N_{\mathbb{Q(\zeta_n)}/K}\mathfrak{P}.$
For $K=\mathbb{Q}$, the latter norm is just $p^f$ where $f$ is the order of $p\pmod{n}$.
For $K=\mathbb{Q}(\zeta_m)$, the former norm is $(a-b)^{\phi(n)/\phi(m)}$ and the latter is $\mathfrak{p}^{f'}$, where $f'$ is the easily-calculated relative residue degree.
This doesn't give you an explicit congruence between $a$ and $b$, but given Gerry's answer, that might have been too much to ask for anyway. On the other hand, for if $\phi(n)/\phi(m)$ is small values of or (as in Alex's answer) if $\phi(n)/\phi(m)$, p$has few factors in$\mathbb{Q}(\zeta_m)$, you get something at least slightly non-stupid out. 2 added 181 characters in body; added 257 characters in body Sure.$a\equiv b\pmod{\mathfrak{P}}$just means$a-b\in\mathfrak{P}$. Taking norms to any subfield$K$of$\mathbb{Q}(\zeta_n)$(e.g.,$\mathbb{Q}$or$\mathbb{Q}(\zeta_m)$) gives you$N_{\mathbb{Q}(\zeta_n)/K}(a-b)\in N_{\mathbb{Q(\zeta_n)}/K}\mathfrak{P}.$For$K=\mathbb{Q}$, the latter norm is just$p^f$where$f$is the order of$p\pmod{n}$. For$K=\mathbb{Q}(\zeta_m)$, the former norm is$(a-b)^{\phi(n)/\phi(m)}$and the latter is$\mathfrak{p}^{f'}$, where$f'$is the easily-calculated relative residue degree. This doesn't give you an explicit congruence between$a$and$b$, but given Gerry's answer, that might have been too much to ask for anyway. On the other hand, for small values of$\phi(n)/\phi(m)$, you get something at least slightly non-stupid out. 1 Sure.$a\equiv b\pmod{\mathfrak{P}}$just means$a-b\in\mathfrak{P}$. Taking norms to any subfield$K$of$\mathbb{Q}(\zeta_n)$(e.g.,$\mathbb{Q}$or$\mathbb{Q}(\zeta_m)$) gives you$N_{\mathbb{Q}(\zeta_n)/K}(a-b)\in N_{\mathbb{Q(\zeta_n)}/K}\mathfrak{P}.$For$K=\mathbb{Q}$, the latter norm is just$p^f$where$f$is the order of$p\pmod{n}\$.