Scala 3, 245 bytes

Golfed version. Attempt This Online!

(n,d)=>{val l=d&(-d);val q=d/l;val i=m(l,q);(((n*i%q)+q)%q,q)}
def m(a:Int,m:Int):Int={def e(a:Int,b:Int):(Int,Int,Int)={if(a==0)(b,0,1)
else{
val (gcd,x1,y1)=e(b%a,a)
val x=y1-(b/a)*x1
val y=x1
(gcd,x,y)
}
}
val (gcd,x,_)=e(a%m,m)
(x%m+m) % m
}

Ungolfed version. Attempt This Online!

object Main {

def pythonMod(a: Int, b: Int): Int = ((a % b) + b) % b


  def mysteriousFunction(numerator: Int, denominator: Int): (Int, Int) = {
    // Extract the lowest set bit from the denominator
    val lowestBit = denominator & (-denominator)
    
    // Calculate the quotient when denominator is divided by its lowest bit
    val quotient = denominator / lowestBit
    
    // Calculate modular inverse of lowestBit modulo quotient
    val inverse = modularInverse(lowestBit, quotient)
    
    // Transform the numerator and return as a tuple
    val newNumerator = pythonMod(numerator * inverse, quotient)
    val newDenominator = quotient
    
    (newNumerator, newDenominator)
  }
  
  def modularInverse(a: Int, m: Int): Int = {
    // Extended Euclidean Algorithm to find modular inverse
    def extendedGcd(a: Int, b: Int): (Int, Int, Int) = {
      if (a == 0) (b, 0, 1)
      else {
        val (gcd, x1, y1) = extendedGcd(b % a, a)
        val x = y1 - (b / a) * x1
        val y = x1
        (gcd, x, y)
      }
    }
    
    val (gcd, x, _) = extendedGcd(a % m, m)
    if (gcd != 1) throw new IllegalArgumentException("Modular inverse does not exist")
    else (x % m + m) % m
  }
  
  def main(args: Array[String]): Unit = {
    val testCasesString = """0/1 -> 0/1
1/1 -> 0/1
2/1 -> 0/1
1/2 -> 0/1
3/2 -> 0/1
1/3 -> 1/3
2/3 -> 2/3
1/6 -> 2/3
5/6 -> 1/3
1/8 -> 0/1
1/10 -> 3/5
3/10 -> 4/5
7/10 -> 1/5
6/5 -> 1/5
13/6 -> 2/3
-1/1 -> 0/1
-1/6 -> 1/3
-1/12 -> 2/3
-3/2 -> 0/1"""
    
    val testCases = testCasesString.split("\n")
    
    for (testCase <- testCases) {
      val parts = testCase.split(" -> ")
      val inputPart = parts(0)
      val expectedOutputPart = parts(1)
      
      // Parse input fraction
      val inputParts = inputPart.split("/")
      val inputFraction = (inputParts(0).toInt, inputParts(1).toInt)
      
      // Parse expected output fraction
      val outputParts = expectedOutputPart.split("/")
      val expectedOutput = (outputParts(0).toInt, outputParts(1).toInt)
      
      // Test the function
      val actualOutput = mysteriousFunction(inputFraction._1, inputFraction._2)
      
      // Verify the result matches expectation
      assert(actualOutput == expectedOutput, 
        s"Failed for ${inputFraction}: got ${actualOutput}, expected ${expectedOutput}")
    }
    
    println("All test cases passed!")
  }
}

Charcoal, 26 bytes

Ｎθ≔＆θ±θζ≧÷ζθＩ⟦θ⌕﹪⁻×…⁰θζＮθ⁰

Try it online! Link is to verbose version of code. Takes q and p as inputs and outputs q' and p'. Explanation: Port of @Tbw's Uiua answer.

Ｎθ≔＆θ±θζ≧÷ζθ

Input q and calculate 2ᵏ and q'.

Ｉ⟦θ⌕﹪⁻×…⁰θζＮθ⁰

Input p and print q' and find p' as the index where 2ᵏp'-p≡0 (mod q').

Python 3.8 (pre-release), 42 bytes

lambda x,y:(x*pow(z:=y&-y,-1,t:=y//z)%t,t)

Try it online!

Input is f(numerator, denominator) and output is (numerator, denominator)

Uiua 0.17.0-dev.1, 23 bytes ^SBCS

⊗0⤚◿⊙-⊙×⟜⇡⍢⊓÷₂×₂(¬◿2)⊙1

Try on Uiua Pad!

Takes q p on stack and outputs p' q'.

This code factors \$q = q'\cdot2^k\$, then finds the integer \$p'\$ between \$0\$ and \$q'-1\$ such that \$p \equiv2^kp' \pmod{q'}\$.