Suppose we have a rod of length $l$ at rest in the unprimed frame and we watch an observer in the primed frame speeding past:

We'll take the origins in both frames to coincide when the observer in the primed frame passes the first end of the rod, so Event A is $(0, 0)$ in both frames.
In the unprimed frame the far end of the rod is at $x = l$, and we see the speeding observer pass it at $t = l/v$, so Event B is $(l/v, l)$. The interval between these events is therefore:
$$ s^2 = \frac{c^2l^2}{v^2} - l^2 $$
In the primed frame the stationary observer sees the rod, of length $l'$ coming towards him at speed $v$. The $x$ coordinate of both events is zero, and the time of Event B is $t = l'/v$, so the interval is:
$$ s'^2 = \frac{c^2 l'^2}{v^2} $$
The intervals must be the same, $s^2 = s'^2$, so:
$$ \frac{c^2 l'^2}{v^2} = \frac{c^2l^2}{v^2} - l^2 $$
and a quick rearrangement gives:
$$ l'^2 = l^2 \left(1 - \frac{v^2}{c^2} \right) $$
$$ l' = l \sqrt{1 - \frac{v^2}{c^2} } = \frac{l}{\gamma} $$
Response to comment:
To work out the time dilation you use a different pair of events. In the unprimed frame you have a clock, ticking with period $T$, stationary at the origin. So the events for the first and second ticks are $(0, 0)$ and $(T, 0)$. The interval $s^2 = c^2 T^2$.
As usual we choose the primed frame so the origins of the frames coincide, and the first tick is at $(0, 0)$. The second tick is at $t = T'$, and because the clock is moving at velocity $v$, the $x$ coordinate of the second tick is $x = vT'$ giving $(T', vT')$. The interval is therefore $s^2 = c^2T'^2 - v^2T'^2$.
As before, we set the intervals equal so:
$$ c^2 T^2 = c^2T'^2 - v^2 T'^2 $$
or:
$$ T'^2 = T^2 \frac{c^2}{c^2 - v^2} $$
Now just divide the top and bottom of the RHS by $c^2$ and take the square root to get:
$$ T' = T \frac{1}{\sqrt{1 - v^2/c^2}} $$