Yup, the fairy drops it. The shell puzzle with the turtle? There are 4 hints to find, all in B1F.
Drop rate is luck dependant, but you can get more drops by getting high combos. Fish spinning is how you can harvest scales from fishes in the ocean, you'll have to look for the green ones to get the rare scales. As for the cyan puzzle, did you solve it as yellow first? You won't be able to do the cyan solution otherwise.