A Better Circular Saw - Hammerhead
First Available: Chapter 2
Other Requirements: Defeat Loqi
Location: Hammerhead
Rewards: 2,000 EXP & Circular Saw Plus
You're able to accept this quest after obtaining the Circular Saw item which you get for defeating Loqi at the end of Chapter 2 of the game's main story. For this quest you'll need to obtain a Sky Gemstone item and bring it to Cid which he will use to upgrade your Circular Saw item.
You can obtain a Sky Gemstone one of two ways, the first and easiest is to pick it up in Lestallum on a white table by the main street going through the city. If you'd like to see the exact location of it in Lestallum use my Chapter 3 Lestallum Treasures Guide. Alternatively, you can obtain this item from the Chapter 8: Seaworthy story mission.
Last but not least you're able to obtain a Sky Gemstone from the A Feline Feast side quest which you get right in Cape Caem from a cat. If you didn't complete the Kitty Catering quest in Galdin Quay involving this cat earlier in the game then this quest won't be available until you do.
List of Sky Gemstone Locations:
1. Lestallum Ontop of a table
2. Chapter 8: Seaworthy Story Mission
3. A Feline Feast Side Quest
4. Found in many of the Menace Dungeons during the Menace Beneath Lucis Side Quest