Android 7.0 introduces a new signature scheme,
V2.
The V2 scheme signs the entire APK rather than just the JAR, as is done in the V1 scheme.
If you sign with only V2, and attempt to install on a pre-7.0 target, you'll get this error since the JARs themselves are not signed and the pre-7.0 PackageManager cannot detect the presence of the V2 APK signature.
To be compatible with all target systems, make sure the APK is signed with both schemes by checking both signature version boxes in Android Studio's
Generate Signed APK dialog as shown here: