Factoring out a $7$ from $3^{35}-5$?

Question

Please Note: My main concern now is how to factor $7$ from $3^{35}-5$ using Algebraic techniques, not how to solve the problem itself; the motivation is just for background.

Motivation:

I was trying to solve the following problem

What is the remainder when $10^{35}$ is divided by $7$?

I used the binomial formula: $\dfrac {(7+3)^{35}}{7}= \dfrac {7^{35} + \cdot \cdot \cdot 3^{35}}{7}= \dfrac {7^{35} + \cdot \cdot \cdot + 35 \cdot 3^{34} \cdot 7}{7} + \dfrac {3^{35}}{7}$

Therefore, $10^{35}$ will have the same remainder as $3^{35}$ when divided by $7$.

I was stuck here, and I wanted to try to reverse engineer the answer. I know the remainder is $5$. Therefore I should be able to write $3^{35} -5 + 5$ as $7k+5$. However, I have no idea how to factor out a $7$ from $3^{35}-5$, or from $10^{35}-5.$ How could I find this $k$ non-explicitly?

Answer 1

If you insist on algebraic techniques then note $\ 3(3^{35}-5)\, =\, (3^{36}-1)-14$

and $\,\ 7 = \color{#c00}{3^2\!-\!3\!+\!1}\mid 3^6\!-\!1\mid 3^{36}-1\ $ so $\,7\,$ divides both summands above, so $\,7\mid 3^{35}\!-\!5$

where $\ \color{#c00}{x^2-x+1}\mid x^6-1\ $ since it divides the $\,\rm\color{#c00}{difference\ of\ squares}\,$ below

$$ x^6-1\ =\, (x^2-1)\,(\!\overbrace{x^4+x^2+1}^{\Large\color{#c00}{ (x^2+1)^2-x^2}}\!)$$

Remark $\ $ "Algebraic" factors that arise arise from polynomial factorizations are heavily employed when factoring integers of the form $\rm\:b^n\pm 1.\:$ A good place to learn about such is Wagstaff's splendid introduction to the Cunningham Project, whose goal is to factor numbers of the form $\rm\:b^n\pm 1.\:$ There you will find mentioned not only old results such as Legendre (primitive divisors of $\rm\:b^n\pm 1\:$ are $\rm\,\equiv 1\pmod{2n},$ but also newer results, e.g. those exploiting cyclotomic factorizations. e.g. see below.

---

Often number identities are more perceptively viewed as special cases of function or polynomial identities. For example, Aurifeuille, Le Lasseur and Lucas discovered so-called Aurifeuillian factorizations of cyclotomic polynomials $\rm\;\Phi_n(x) = C_n(x)^2 - n\ x\ D_n(x)^2\;$. These play a role in factoring numbers of the form $\rm\; b^n \pm 1\:$, cf. the Cunningham Project. Below are some simple examples of such factorizations (e.g. see below).

$$\begin{array}{rl} x^4 + 2^2 \quad=& (x^2 + 2x + 2)\;(x^2 - 2x + 2) \\[0.5em] \dfrac{x^6 + 3^2}{x^2 + 3} \quad=& (x^2 + 3x + 3)\;(x^2 - 3x + 3) \\[0.5em] \dfrac{x^{10} - 5^5}{x^2 - 5} \quad=& (x^4 + 5x^3 + 15x^2 + 25x + 25)\;(x^4 - 5x^3 + 15x^2 - 25x + 25) \\[0.5em] \dfrac{x^{12} + 6^6}{x^4 + 36} \quad=& (x^4 + 6x^3 + 18x^2 + 36x + 36)\;(x^4 - 6x^3 + 18x^2 - 36x + 36) \end{array}$$

Answer 2

By Fermat's little theorem, $3^6\equiv 1 \bmod 7$, so that $3^{35}\equiv 3^5\equiv 5\bmod 7$. Hence $7\mid (3^{35}-5)$, and explicitly, $3^{35}=7\cdot 7147363585571386.$

Edit: "shifting interest to the factorisation": $$3^{35}-5=2\cdot 7\cdot 1729363\cdot 2066472911,$$ using integer factorisation algorithms.

Answer 3

You can use the fact that the remainder of $ab$ is the remaineder of $a$ multiplied by the remaineder of $b$. So forgeting factors of $7$, we have $3^{35}=27*3^{32}=6*(9)^{16}=6*2^{16}=6*(16)^4=6*2^4=6*2=5$

Answer 4

Do you know Fermat little theorem?

for prime $p, n^p \equiv n \mod p\\ n^{p-1}\equiv 1 \mod p$

$10^35 = (10^6)^5(10^5)\\ 10^35 \equiv (10^5) \mod 7\\ 10^35 \equiv 5 \mod 7$

Alternative:

You could say, $10^{35} -1 = (10^7 - 1)(10^{28} + 10^{21} + 10^{14} + 10^7 + 1)$

And the remainder of the product equals the product of the remainders.

$(10^7 - 1)(10^{28} + 10^{21} + 10^{14} + 10^7 + 1) / 7\\ (3-1)(3^4 + 3^3 + 3^2 + 3 + 1) = 242$

and the remainder of 242/7 = 4

Answer 5

$$\dfrac{10^{35} - 5}{7} = 14285714285714285714285714285714285$$ Well, that's an interesting pattern. $10^6 \equiv 1 \mod 7$ by Fermat, with $\dfrac{10^6-1}{7} = 142857$. So $$\dfrac{10^{36}-1}{7} = \left( 10^{30} + 10^{24} + 10^{18} + 10^{12} + 10^6 + 1\right) \dfrac{10^6-1}{7} = 142857142857142857142857142857142857$$ Now subtract $7$ and divide by $10$ to get $$ \dfrac{\dfrac{10^{36}-1}{7} -7}{10} = \dfrac{10^{36}-50}{10} = \dfrac{10^{35} - 5}{7} $$

EDIT:

There's nothing special about $10$ here, except that it's coprime to $7$ (and that we can see the pattern when writing numbers in base $10$). So we also have

$$ \dfrac{3^{36}-1}{7} = (3^{30} + 3^{24} + 3^{18} + 3^{12} + 3^6 + 1) \dfrac{3^6 - 1}{7} = (3^{30} + 3^{24} + 3^{18} + 3^{12} + 3^6 + 1) \times 104$$ and $$ \dfrac{3^{35}-5}{7} = \dfrac{\dfrac{3^{36}-1}{7} - 2}{3} = (3^{29} + 3^{23} + 3^{17} + 3^{11} + 3^5) \times 104 + 34 $$ which in base $3$ is $1021201021201021201021201021201021$.

Answer 6

As a (possibly) different approach: start by remarking that $$3^3=4\times 7-1$$

It follows that $$3^{33}=(4\times 7-1)^{11}=7N-1$$

Where $N$ is a simple expression in powers of $4$ and $7$ (with some binomial coefficients thrown in for good measure). Specifically $$N=\sum_{i=1}^{11}\binom {11}i (-1)^{11-i}4^i7^{i-1}$$

We then remark that $$3^{35}-5=3^{33}3^2-5=(7N-1)\times 9-5 = 7\times 9N-9-5=7\times (9N-2)$$