  We investigate the relation between two approaches to the characterisation of
quantum Markovianity, divisibility and lack of information backflow. We show
that a bijective dynamical map is completely-positive-divisible if and only if
a monotonic non-increase of distinguishability is observed for two equiprobable
states of the evolving system and an ancilla. Moreover our proof is
constructive: given any such map that is not completely-positive-divisible, we
give an explicit construction of two states that, when taken with the same a
priori probability, exhibit information back-flow. Finally, while an ancilla is
necessary for the equivalence to hold in general, we show that it is always
possible to witness the non-Markovianity of bijective maps without using any
entanglement between system and ancilla.
