Even if the physical device (phone, tablet, etc.) remains the same, when (re-)installing the mobile application the link between your mobile application and your EU Login account is broken and needs to be re-established in the same way you would add a new device.
To avoid mistaking devices, you should first erase the existing link before re-installing the mobile app or registering the new one.
You have another second factor configured?
This is excellent news! In this case you may use it to access the "Manage my mobile devices" option available in My Account
From there, first delete the existing mobile device, then add the "new" one. You may follow the related instructions How can I add a mobile device to my EU Login account?
You do not have any other second factor configured?
If you lost access to your only second factor, things may be a little more complicated depending on your account type.
Please first check which account type you are using by following these simple instructions EU Login Help & Frequently Asked Questions
You are using an external, self-registered account?
If you have an external account, follow the instructions from An application requires a second factor authentication, but I do not have access to it anymore
This will guide you through the process of removing all second factors, allowing you to add new ones afterwards.
You are using an internal, EU Institution staff member account?
As long as it is not deprecated, you may updated your mobile phone number through your HR system (SYSPER, Streamline...) to use the Password + SMS authentication option. The replication of your phone number from your HR system to EU Login may take up to 24h however. This is why it is very important to have multiple second factors configured with your account. You may as well contact your support team to assist you.
After successfully logging in, follow the instructions from What second factor can I configure with my account? to add another second factor. Please do not forget to delete the existing mobile device that is no more useable!