Emperor Justinian and Empress Theodora were both

rulers of Gaul.
rulers of Jerusalem
rulers of Byzantium.
rulers of Rome.

Emperor Justinian and Empress Theodora were both rulers of Byzantium.