Solveeit Logo
Login

Question

Question: How many natural numbers n ≤ 105 are there such that 7 exactly divides $2^n - n^2$...

How many natural numbers n ≤ 105 are there such that 7 exactly divides 2n−n22^n - n^2

Answer

30

Explanation

Solution

We need to find the number of natural numbers n≤105n \le 105 such that 2n−n2≡0(mod7)2^n - n^2 \equiv 0 \pmod{7}, or 2n≡n2(mod7)2^n \equiv n^2 \pmod{7}.

  1. Powers of 2 modulo 7: 21≡22^1 \equiv 2, 22≡42^2 \equiv 4, 23≡1(mod7)2^3 \equiv 1 \pmod{7}. The cycle length is 3.

    • n≡0(mod3)  ⟹  2n≡1(mod7)n \equiv 0 \pmod{3} \implies 2^n \equiv 1 \pmod{7}
    • n≡1(mod3)  ⟹  2n≡2(mod7)n \equiv 1 \pmod{3} \implies 2^n \equiv 2 \pmod{7}
    • n≡2(mod3)  ⟹  2n≡4(mod7)n \equiv 2 \pmod{3} \implies 2^n \equiv 4 \pmod{7}

  2. Squares modulo 7:

    • n≡0(mod7)  ⟹  n2≡0(mod7)n \equiv 0 \pmod{7} \implies n^2 \equiv 0 \pmod{7}
    • n≡1,6(mod7)  ⟹  n2≡1(mod7)n \equiv 1, 6 \pmod{7} \implies n^2 \equiv 1 \pmod{7}
    • n≡2,5(mod7)  ⟹  n2≡4(mod7)n \equiv 2, 5 \pmod{7} \implies n^2 \equiv 4 \pmod{7}
    • n≡3,4(mod7)  ⟹  n2≡2(mod7)n \equiv 3, 4 \pmod{7} \implies n^2 \equiv 2 \pmod{7}

  3. Combining conditions using CRT (modulo 21):

    • If n≡0(mod3)n \equiv 0 \pmod{3} (2n≡12^n \equiv 1), we need n2≡1(mod7)n^2 \equiv 1 \pmod{7}, so n≡1,6(mod7)n \equiv 1, 6 \pmod{7}.
      • n≡0(mod3),n≡1(mod7)  ⟹  n≡15(mod21)n \equiv 0 \pmod{3}, n \equiv 1 \pmod{7} \implies n \equiv 15 \pmod{21}.
      • n≡0(mod3),n≡6(mod7)  ⟹  n≡6(mod21)n \equiv 0 \pmod{3}, n \equiv 6 \pmod{7} \implies n \equiv 6 \pmod{21}.
    • If n≡1(mod3)n \equiv 1 \pmod{3} (2n≡22^n \equiv 2), we need n2≡2(mod7)n^2 \equiv 2 \pmod{7}, so n≡3,4(mod7)n \equiv 3, 4 \pmod{7}.
      • n≡1(mod3),n≡3(mod7)  ⟹  n≡10(mod21)n \equiv 1 \pmod{3}, n \equiv 3 \pmod{7} \implies n \equiv 10 \pmod{21}.
      • n≡1(mod3),n≡4(mod7)  ⟹  n≡4(mod21)n \equiv 1 \pmod{3}, n \equiv 4 \pmod{7} \implies n \equiv 4 \pmod{21}.
    • If n≡2(mod3)n \equiv 2 \pmod{3} (2n≡42^n \equiv 4), we need n2≡4(mod7)n^2 \equiv 4 \pmod{7}, so n≡2,5(mod7)n \equiv 2, 5 \pmod{7}.
      • n≡2(mod3),n≡2(mod7)  ⟹  n≡2(mod21)n \equiv 2 \pmod{3}, n \equiv 2 \pmod{7} \implies n \equiv 2 \pmod{21}.
      • n≡2(mod3),n≡5(mod7)  ⟹  n≡5(mod21)n \equiv 2 \pmod{3}, n \equiv 5 \pmod{7} \implies n \equiv 5 \pmod{21}.

    The possible residues modulo 21 are {2,4,5,6,10,15}\{2, 4, 5, 6, 10, 15\}. There are 6 such residues.

  4. Counting numbers up to 105: Numbers are of the form n=21k+rn = 21k + r, where r∈{2,4,5,6,10,15}r \in \{2, 4, 5, 6, 10, 15\}. We need 1≤21k+r≤1051 \le 21k + r \le 105. For each of the 6 residues, kk can range from 0 up to ⌊105−r21⌋\lfloor \frac{105-r}{21} \rfloor. For r=2r=2, k≤⌊10321⌋=4k \le \lfloor \frac{103}{21} \rfloor = 4. k∈{0,1,2,3,4}k \in \{0,1,2,3,4\} (5 values). For r=4r=4, k≤⌊10121⌋=4k \le \lfloor \frac{101}{21} \rfloor = 4. k∈{0,1,2,3,4}k \in \{0,1,2,3,4\} (5 values). ... For r=15r=15, k≤⌊9021⌋=4k \le \lfloor \frac{90}{21} \rfloor = 4. k∈{0,1,2,3,4}k \in \{0,1,2,3,4\} (5 values). Since 105=5×21105 = 5 \times 21, each residue class has exactly 5 numbers in the range [1, 105]. Total count = 6 residues×5 numbers/residue=306 \text{ residues} \times 5 \text{ numbers/residue} = 30.