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 EU Login Mobile app installation
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?
If you do not have a second authentication option, you will need to contact the appropriate helpdesk and request a reset of your authentication methods so that you can enroll a new one.
For this reason, it is very important to have multiple authentication factors configured for your account.