Why does Lagrange's break down here? If we remove the condition to be working modulo $p$ prime. Why does the theorem no longer hold? Would I be correct in thinking it is because in the induction we say $f(X)\equiv(X-a)g(X)$ so potentially if $f(X)\equiv0$ then one of the cases to consider is $X\equiv a \mod p$ which has at most one solution?. (I think maybe this is where it would break down if we worked modulo not a prime) But I can't see why explicitly it wouldn't work.
I didn't state the theorem of proof for the sake of brevity as I assume it is well known but if you need any clarification just ask.
Thanks! 
Suppose that $p$ is prime and that
$f(X)$ is a polynomial with integer coefficients and degree $d ≥ 0$. Then the
equation
$f(X) ≡ 0 \mod p$
has at most $d$ distinct solutions modulo $p$.
 A: You are close.  The essence of the issue is a careful analysis of the little theorem:
If $ab \equiv 0 \pmod{m}$, then $a \equiv 0 \pmod{m}$ or $b \equiv 0 \pmod{m}$.  If $m$ is prime, this is true, and is just a restatement of Euclid's Lemma:  https://en.wikipedia.org/wiki/Euclid's_lemma.
But it never holds modulo a composite $m$.  To see this, simply let $m = ab$ with $a$ and $b$ proper factors of $m$.  
So back to your question, the problem is with the induction after writing
$$ f(x) \equiv (x-a) g(x) \pmod{m}$$
We would then like to say that the remaining roots of $f$, other than $a$, are all roots of $g$.  If $b \not\equiv a \pmod{m}$ is such that $f(b) \equiv 0 \pmod{m}$, then
$$ 0 \equiv (b-a) g(b) \pmod{m}$$.
We assumed that $b - a \not\equiv 0 \pmod{m}$.  If $m$ is a prime, then by Euclid's Lemma, we can say $g(b) \equiv 0 \pmod{m}$.  One can then finish up the induction.  
But if $m$ is composite, then it may be that $g(b) \not\equiv 0 \pmod{m}$ and the proof breaks down.
For example, let $m=65$, $f = x^2 + 1$, and $a=8$.  Then
$$ f(x) \equiv (x-8)(x+8) \pmod{65}, $$  
so we may set $g(x) = x+8$.  But $f(18) \equiv 0 \pmod{65}$, and $g(18) \not\equiv 0 \pmod{65}$.
Notice that we could instead have started with the root $18$ and factored $f(x) \equiv (x-18)(x+18) \pmod{65}$.  We can always factor a linear term out from $f$ corresponding a root of $f$ -- but with a composite modulus, if you fix two distinct roots, you may not be able to factor out linear terms corresponding to both roots simultaneously.
