diff --git a/rrs/tools/rrs_distros.py b/rrs/tools/rrs_distros.py
index 55f5aeb..8fc7ffb 100755
--- a/rrs/tools/rrs_distros.py
+++ b/rrs/tools/rrs_distros.py
@@ -74,16 +74,21 @@ def search_package_in_distros(pkglst_dir, recipe, data):
         (distro, distro_release) = distro_file.split("-")
 
         if distro.lower() in distro_aliases:
-            pn = distro_aliases[distro.lower()]
+            names = [distro_aliases[distro.lower()]]
         else:
-            pn = recipe_name
+            names = [recipe_name]
+            # Fedora and openSUSE call the source package for a Python
+            # module python-<name>. Debian's lists have the python3-<name>
+            # binary package, which OE-Core's distro_check records too.
+            if recipe_name.startswith('python3-'):
+                names.append('python-' + recipe_name[len('python3-'):])
 
         with open(os.path.join(pkglst_dir, distro_file), "r") as f:
             for line in f:
                 (pkg, section) = line.split(":")
-                if pn == pkg:
+                if pkg in names:
                     distro_complete = distro + "-" + section[:-1]
-                    distros[distro_complete] = pn
+                    distros[distro_complete] = pkg
                     break
 
     return distros
diff --git a/tests/test_rrs_distros.py b/tests/test_rrs_distros.py
index 419b44d..45d1759 100644
--- a/tests/test_rrs_distros.py
+++ b/tests/test_rrs_distros.py
@@ -43,3 +43,13 @@ def test_native_suffix_is_ignored(rrs_distros, pkglst_dir):
 def test_distro_pn_alias(rrs_distros, pkglst_dir):
     assert search(rrs_distros, pkglst_dir, 'liblz4', alias='Debian=lz4 Fedora=lz4') == {'Debian-main': 'lz4', 'Fedora-main': 'lz4'}
 
+
+def test_python3_recipe(rrs_distros, pkglst_dir):
+    # [YOCTO #16513] Debian's list has the python3-brotli binary package,
+    # Fedora's has the python-brotli source package
+    assert search(rrs_distros, pkglst_dir, 'python3-brotli') == {'Debian-main': 'python3-brotli', 'Fedora-main': 'python-brotli'}
+
+
+def test_python3_recipe_not_matched_by_bare_name(rrs_distros, pkglst_dir):
+    # lz4 is the C library, not the Python module
+    assert search(rrs_distros, pkglst_dir, 'python3-lz4') == {}
