How can I fix your device has been modified. Software updates are not available.?

[Protooooo]

"your device has been modified. Software updates are not available."

Also says my device is modified under my Device status. I haven't modified my phone at all! I've tried so much from so many sites but I just can't get anything. I even tried a factory reset and lost my Google account because I don't remember it. I've seen solutions to this problem before but that involved them taking their SD card out, but i have no SD card. The main problem is that my phone is stuck on 4.1.1, and i get "Your device has been modified. Software updates are no available." Please help.

I use a Galaxy S3.

 

[Almeuit]

Re: "your device has been modified. Software updates are not available."

Did you buy the phone used? That is the usual message you get when the phone has been rooted.

 

[Protooooo]

Re: "your device has been modified. Software updates are not available."

I found out it's been rooted at one point and time but the root was taken off. Is there any way to change the modified message still?