This problem has occurred to me on many devices before.
Some of the most common reasons are:
- Date and time are incorrect
- Device is not original (playstore manually installed)
- Google play services corrupted
Try seeing if you have any of those reasons above.
Date and time is the most common for me. Also if these don't work please root your device and install a custom rom with playstore pre-installed.