@Kjetil Jarstein
It is an expected behavior. On first attempt, users will be prompted to install the Microsoft Authenticator on iOS or the Intune Company Portal on Android.
Thereafter, you will be able to make use of SSO on the Edge Browser.
Here's a blog that would help you understand and configure the steps to enable the same - https://techcommunity.microsoft.com/t5/Enterprise-Mobility-Security/Microsoft-Edge-on-iOS-and-Android-now-supports-conditional/ba-p/476091
-----------------------------------------------------------------------------------------
Do click on "Mark as Answer" on the post that helps you, this can be beneficial to other community members.