Black cats are NOT the witch's cats. It's the GRAY cat! Specifically, a "grimalkin" cat.
Grimalkins are mentioned in a few major works of literature throughout history.
"Beware the Cat" by William Baldwin, published in 1570, is a story about talking cats. This is, probably, one of the first major mentions of evil cats in popular literature. The main cat in in the story was a grimalkin.
A grimalkin appears in Hawthorne's "House of the Seven Gables" where the gray cat, chasing a mouse is compared to the devil chasing a person's soul. Hey! This is Salem, Massachusetts we're talking about, here! The home of the Witch Trials! If a gray can from Salem was the devil, it must be true! Right?
Finally, we have the granddaddy of them all... Macbeth!
It was a grimalkin cat, specifically written by Shakespeare, that was the familiar of the three "Weird Sisters." (AKA: witches.)
If it was good enough for The Bard, it's good enough for me.
It is also a legend that Nostradamus had a cat named "Grimalkin."
If you don't believe me, check Wikipedia. Everything I just said is spelled out, right there: