Let $m$ be a square-free number. I want to prove that, given some $b \in \mathbb{Z}^+$, where $\gcd(b,m)>1$, that
$\qquad b^{\,c\,\phi(m) + 1} \equiv b \pmod m,\ $ for some $c \in \mathbb{Z}^+$.
I've verified this with a bunch of different values of $m$ and $b$, but I'm really stuck on how to prove it.
Let $b=p_1^{a_1}p_2^{a_2}\ldots p_k^{a_k}$, where $p_1, p_2, \ldots p_k$ are prime divisors of b. We'll prove there exist $c$ (actually every natural number works), such that:
$$p_1^{a_1(c\phi(m)+1)} \equiv p_1^{a_1} \pmod {m}$$ $$p_2^{a_2(c\phi(m)+1)} \equiv p_2^{a_2} \pmod {m}$$ $$\cdots$$ $$p_k^{a_k(c\phi(m)+1)} \equiv p_k^{a_k} \pmod {m}$$
Get the first relation and divide with $p_1^{a_1}$ since $m$ is square integer, one is the highest power $p_1$ that devides it. Now we get:
$$p_1^{a_1c\phi(m)} \equiv 1 \pmod n$$
where $n=\frac m{gcd(m,p_1)}$, obviously $(n,p_1) = 1$ since m is squarefree integer. Now use the fact that the Euler Totient Function is multiplicative for relatively prime numbers and that $p_1^{\phi(n)} \equiv 1 \pmod n$:
$$p_1^{a_1c\phi(m)} \equiv p_1^{a_1c\phi(n) \phi(p_1)} \equiv (p_1^{\phi(n)})^{a_1c\phi(p_1)} \equiv 1^{a_1c\phi(p_1)} \equiv 1 \pmod n$$
Simularly we prove for each of the congruence relations.
Now just multiply all the congruence relations and we have:
$$(p_1^{a_1}p_2^{a_2}\ldots p_k^{a_k})^{c\phi(m) + 1} \equiv p_1^{a_1}p_2^{a_2}\ldots p_k^{a_k} \pmod m$$ $$b^{c\phi(m) + 1} \equiv b \pmod m$$
Hence the proof.
You can directly prove this by using a nice lemma that another MSE user has proved: here. Subsitute $e=c\phi(m) + 1$ in his answer and use that $p-1 = \phi(p)$ and the fact that $m$ is squarefree.