Yes, the synchronise ability shall help you find a Pokemon with the same nature, as long as the synchroniser is the leading party Pokemon.
People are underestimating our dear own site.
"If a Pokémon with Synchronize is the leading party Pokémon, there is a 50% chance of each wild Pokémon encountered having the same nature."
Just ensure your elgyem occupies first slot in your party. Fainted Pokemon also work, but consider teaching your elgyem hypnosis or thunder wave.
Hope this helped!