  We consider a fair division setting in which $m$ indivisible items are to be
allocated among $n$ agents, where the agents have additive utilities and the
agents' utilities for individual items are independently sampled from a
distribution. Previous work has shown that an envy-free allocation is likely to
exist when $m=\Omega(n\log n)$ but not when $m=n+o(n)$, and left open the
question of determining where the phase transition from non-existence to
existence occurs. We show that, surprisingly, there is in fact no universal
point of transition---instead, the transition is governed by the divisibility
relation between $m$ and $n$. On the one hand, if $m$ is divisible by $n$, an
envy-free allocation exists with high probability as long as $m\geq 2n$. On the
other hand, if $m$ is not "almost" divisible by $n$, an envy-free allocation is
unlikely to exist even when $m=\Theta(n\log n/\log\log n)$.
