This should help you.
The Game Data is saved on the Game Card itself. This explains why you can hop from 3DS to 3DS with the same cartridge and have the same progress on both 3DSes.
And your Friend Code does change after formatting. Some people do this just for Ditto Safaris.