I cannot add my Microsoft Exchange and Gmail accounts to Apple Mail.

canadiguzel wrote:

When I want to add one of them, a new pop-up opens stating that authentication needs to be done via browser, then I receive the same error for both: Authentication failed.

They were all working fine, until last week, then there were synchronization problems. As I have to change passwords on both accounts. I have removed both accounts to add them again to solve the problem, but not I cannot even add new accounts to Apple mail.

Try changing your default browser to Safari and compare your results

Make Safari your default web browser on Mac - Apple Support

Mail User Guide for Mac - Apple Support

Try app specific passwords

https://support.microsoft.com/en-us/account-billing/using-app-passwords-with-apps-that-don-t-support-two-step-verification-5896ed9b-4263-e681-128a-a6f2979a7944#:~:text=Go%20to%20the%20Security%20basics%20page%20and%20sign,your%20normal%20Microsoft%20account%20password%20in%20the%20application.

https://support.google.com/mail/answer/185833?hl=en

I suggest that working with Microsoft and Gmail directly may be the best solution. Good luck.