A divide by 2 logic device might do the trick if i opt for a 50% reduction in frequency vbut how to do that with a pic?
50% isn't hard (though a hardware flip/flop is even easier). Just wire the input signal to INT0 for example, set it up to interrupt on the rising (or falling) edge, toggle the output signal each interrupt. If you need anything but 50% you really need to measure the frequency/pulsewidth, calculate the new frequency/period and either adjust the period of a timer interrupt or use the CCP module to generate the desired output frequency.

/Henrik.