very difficult congruence

[logistic_guy]

here is the question

Find all solutions of $\displaystyle x^4 - 13x^3 + 11x - 3 \equiv 0 \ (mod \ 7^8)$.

my attemb
is there a way to solve this or i've to use a computer?

 

[fresh_42]

What remains after you eliminated the solution $x=-1\equiv 5,764,800 \pmod{7^8}$?

 

[logistic_guy]

What remains after you eliminated the solution $x=-1\equiv 5,764,800 \pmod{7^8}$?

thank

i don't understand what you mean by eliminating the solution, but i see you get lucky to find an negative integer solution make the polynomial equal zero. what happen if the polynomial don't have negative integer solutions like this

$\displaystyle x^9 + 13x^3 - x + 100336 \equiv 0 \ (mod \ 17^9)$.

 

[fresh_42]

There are no golden rules that I know of. $f(x) \equiv 0 \pmod{p^n}$ only means that $p\,|\,p^n\,|\,f(x)$ from where you can start. Things quickly become complicated if you cannot factor $f(x) .$

 

[Agent Smith]

$y = x^4 - 13x^3 + 11x - 3$

$x + 1 = 7^8$

Shooting in the dark

 

[logistic_guy]

There are no golden rules that I know of. $f(x) \equiv 0 \pmod{p^n}$ only means that $p\,|\,p^n\,|\,f(x)$ from where you can start. Things quickly become complicated if you cannot factor $f(x) .$

thank

$\displaystyle p\,|\,p^n\,|\,f(x)$

what this mean? say it in words

View attachment 38733
$y = x^4 - 13x^3 + 11x - 3$

$x + 1 = 7^8$

Shooting in the dark

shooting in the dark?

 

[fresh_42]

thank

$\displaystyle p\,|\,p^n\,|\,f(x)$

what this mean? say it in words

It means that $p$ divides $p^n$ and $p^n$ divides $f(x)$ and so $p$ divides $f(x).$

If a prime divides a product, then it has to divide one of the factors. This is the definition of a prime. This makes it important to factor $f(x)=g(x)\cdot h(x)$ so that if $p$ divides $f(x)$ it means that $p$ divides $g(x)$ or $p$ divides $h(x)$ or both. That's all you can say.

Your second equation $f(x)=x^9+13x^3-x+100336 =x^9+13x^3-x+2^4\cdot 6271\equiv x^9-4x^3-x+2\pmod{17}$ cannot be factored without using numerical approximations, so $17^9$ divides $f(x)$ doesn't lead to any information. It is probably more promising to host a séance and ask Ramanujan. For us less gifted there is only the possibility of asking a machine. Wolfram Alpha says
$$f(x)\equiv 0\pmod{17^9}\Longleftrightarrow x = 118587876497 n + 3641456693 \quad( n \in \mathbb{Z}).$$

 

[logistic_guy]

It means that $p$ divides $p^n$ and $p^n$ divides $f(x)$ and so $p$ divides $f(x).$

If a prime divides a product, then it has to divide one of the factors. This is the definition of a prime. This makes it important to factor $f(x)=g(x)\cdot h(x)$ so that if $p$ divides $f(x)$ it means that $p$ divides $g(x)$ or $p$ divides $h(x)$ or both. That's all you can say.

Your second equation $f(x)=x^9+13x^3-x+100336 =x^9+13x^3-x+2^4\cdot 6271\equiv x^9-4x^3-x+2\pmod{17}$ cannot be factored without using numerical approximations, so $17^9$ divides $f(x)$ doesn't lead to any information. It is probably more promising to host a séance and ask Ramanujan. For us less gifted there is only the possibility of asking a machine. Wolfram Alpha says
$$f(x)\equiv 0\pmod{17^9}\Longleftrightarrow x = 118587876497 n + 3641456693 \quad( n \in \mathbb{Z}).$$

thank fresh_42 very much

you explained it nicely

the book say the answer $\displaystyle x = 3641456693$ wolfram say $\displaystyle x = 118587876497 n + 3641456693$

i've three questions. do this mean the book answer isn't all solutions? if i get $\displaystyle x = 3641456693$ by any method, how to get the other one $\displaystyle 118587876497n$? they're related, right?

 

[fresh_42]

thank fresh_42 very much

you explained it nicely

the book say the answer $\displaystyle x = 3641456693$ wolfram say $\displaystyle x = 118587876497 n + 3641456693$

i've three questions. do this mean the book answer isn't all solutions? if i get $\displaystyle x = 3641456693$ by any method, how to get the other one $\displaystyle 118587876497n$? they're related, right?

Yes. We only have answers modulo $17^9= 118587876497.$ The number $3641456693$ is one solution, that repeats every $118587876497$ numbers again in both directions. You can test e.g. $3641456693+ 118587876497=122229333190$ or $3641456693- 118587876497=-114946419804$. However, the ninth powers of them don't look nice.

Say we set $x_0=3641456693$ for which we know that $x_0^9+13x_0^3-x_0+100336\equiv 0\pmod{17^9}.$ Then

$$\begin{array}{lll} \displaystyle{ (x_0+17^9\cdot n)^9+13(x_0+17^9\cdot n)^3-(x_0+17^9\cdot n)+100336}\\[12pt] \displaystyle{=\left(\sum_{k=0}^9 \binom{9}{k}x_0^{9-k}(17^9)^k\right)+13\left(\sum_{k=0}^3 \binom{3}{k}x_0^{3-k}(17^9)^{k}\right)-17^9\cdot n-x_0+100336}\\[18pt] \displaystyle{=\left(x_0^9+\sum_{k=1}^9 \binom{9}{k}x_0^{9-k}(17^9)^k\right)+13\left(x_0^3+\sum_{k=1}^3 \binom{3}{k}x_0^{3-k}(17^9)^{k}\right)-17^9\cdot n-x_0+100336}\\[18pt] \equiv x_0^9+13\cdot x_0^3 -x_0+100336 \pmod{17^9}\\[12pt] \equiv 0\pmod{17^9}\\[12pt] \end{array}$$This was the proof that all numbers $x_0+17^9\cdot n$ are also solutions. I thought that the proof was easier to handle than testing so large numbers.

I asked a computer to solve it for me. How did you find the solution?

 

[Agent Smith]

thank

$\displaystyle p\,|\,p^n\,|\,f(x)$

what this mean? say it in words


shooting in the dark?

$x^4 - 13x^3 + 11x - 3 = (x + 1)(x^3 - 14x^2 + 14x - 3)$
So $x + 1 = 7^8n$ or $x^3 - 14x^2 + 14x - 3 = 7^8m$. That's what I thought anyway. Just like how $8 \not |\text{ } 12$ and $8 \not | \text{ } 10$, but $8 | 120$, same thing I guess.

You could try distributing the eight $7$s among the $2$ factors.

 

[logistic_guy]

Yes. We only have answers modulo $17^9= 118587876497.$ The number $3641456693$ is one solution, that repeats every $118587876497$ numbers again in both directions. You can test e.g. $3641456693+ 118587876497=122229333190$ or $3641456693- 118587876497=-114946419804$. However, the ninth powers of them don't look nice.

thank

Say we set $x_0=3641456693$ for which we know that $x_0^9+13x_0^3-x_0+100336\equiv 0\pmod{17^9}.$ Then

$$\begin{array}{lll} \displaystyle{ (x_0+17^9\cdot n)^9+13(x_0+17^9\cdot n)^3-(x_0+17^9\cdot n)+100336}\\[12pt] \displaystyle{=\left(\sum_{k=0}^9 \binom{9}{k}x_0^{9-k}(17^9)^k\right)+13\left(\sum_{k=0}^3 \binom{3}{k}x_0^{3-k}(17^9)^{k}\right)-17^9\cdot n-x_0+100336}\\[18pt] \displaystyle{=\left(x_0^9+\sum_{k=1}^9 \binom{9}{k}x_0^{9-k}(17^9)^k\right)+13\left(x_0^3+\sum_{k=1}^3 \binom{3}{k}x_0^{3-k}(17^9)^{k}\right)-17^9\cdot n-x_0+100336}\\[18pt] \equiv x_0^9+13\cdot x_0^3 -x_0+100336 \pmod{17^9}\\[12pt] \equiv 0\pmod{17^9}\\[12pt] \end{array}$$This was the proof that all numbers $x_0+17^9\cdot n$ are also solutions. I thought that the proof was easier to handle than testing so large numbers.

i don't understand the proof

I asked a computer to solve it for me. How did you find the solution?

the book solution

$x^4 - 13x^3 + 11x - 3 = (x + 1)(x^3 - 14x^2 + 14x - 3)$
So $x + 1 = 7^8n$ or $x^3 - 14x^2 + 14x - 3 = 7^8m$. That's what I thought anyway. Just like how $8 \not |\text{ } 12$ and $8 \not | \text{ } 10$, but $8 | 120$, same thing I guess.

You could try distributing the eight $7$s among the $2$ factors.

i don't see any bullets in your answer. did you miss shooting in the dark?

the one you're solving is easy once we see the -1. you're able to do the same thing to post number 3?

 

[fresh_42]

i don't understand the proof

I only proved that $118587876497\cdot n+3641456693$ is a solution for any integer $n$ if $3641456693$ is a solution. I did not prove how to find $3641456693.$

My proof only used the binomial formula for $(3641456693+ 118587876497\cdot n)^9$ and $(3641456693+ 118587876497\cdot n)^3 .$ These numbers are nasty to write, so I set $x_0=3641456693$ and wrote $17^9$ instead of $118587876497.$

This means that e.g.
$$\begin{array}{lll} (3641456693+ 118587876497\cdot n)^9&=(x_0 + 17^9\cdot n)^9\\[10pt] &= x_0^9 + 9\cdot x_0^8\cdot (17^9) + \dfrac{9\cdot 8}{2}\cdot x_0^7\cdot (17^9)^2+\dfrac{9\cdot 8\cdot 7}{2\cdot 3}\cdot x_0^6\cdot (17^9)^3 +\ldots\\[10pt] &\ldots +\dfrac{9\cdot 8\cdot 7\cdots 3}{2\cdot 3\cdots 6\cdot 7}\cdot x_0^2\cdot (17^9)^7+\dfrac{9\cdot 8\cdot 7\cdots 2}{2\cdot 3\cdots 6\cdot 7\cdot 8}\cdot x_0\cdot (17^9)^8\\[10pt] &+\dfrac{9\cdot 8\cdot 7\cdots 2\cdot 1}{2\cdot 3\cdots 6\cdot 7\cdot 9}\cdot (17^9)^9 \end{array}$$
The notation with the sums $\sum$ only made life easier and typos less likely. The point is: if you take this expression modulo $17^9$ then only $x_0^9$ remains. And the same holds with different coefficients for $(x_0 + 17^9\cdot n)^3.$ This means, if $x_0=3641456693$ is a solution, then we know that
$$\begin{array}{lll} (3641456693+ 118587876497\cdot n)^9&\equiv (3641456693)^9+13\cdot (3641456693)^3 -3641456693 +100336 \\[10pt] &\equiv x_0^9+13x_0^3-x_0+100336 \equiv 0 \pmod{17^9} \end{array}$$

 

[logistic_guy]

I only proved that $118587876497\cdot n+3641456693$ is a solution for any integer $n$ if $3641456693$ is a solution. I did not prove how to find $3641456693.$

My proof only used the binomial formula for $(3641456693+ 118587876497\cdot n)^9$ and $(3641456693+ 118587876497\cdot n)^3 .$ These numbers are nasty to write, so I set $x_0=3641456693$ and wrote $17^9$ instead of $118587876497.$

This means that e.g.
$$\begin{array}{lll} (3641456693+ 118587876497\cdot n)^9&=(x_0 + 17^9\cdot n)^9\\[10pt] &= x_0^9 + 9\cdot x_0^8\cdot (17^9) + \dfrac{9\cdot 8}{2}\cdot x_0^7\cdot (17^9)^2+\dfrac{9\cdot 8\cdot 7}{2\cdot 3}\cdot x_0^6\cdot (17^9)^3 +\ldots\\[10pt] &\ldots +\dfrac{9\cdot 8\cdot 7\cdots 3}{2\cdot 3\cdots 6\cdot 7}\cdot x_0^2\cdot (17^9)^7+\dfrac{9\cdot 8\cdot 7\cdots 2}{2\cdot 3\cdots 6\cdot 7\cdot 8}\cdot x_0\cdot (17^9)^8\\[10pt] &+\dfrac{9\cdot 8\cdot 7\cdots 2\cdot 1}{2\cdot 3\cdots 6\cdot 7\cdot 9}\cdot (17^9)^9 \end{array}$$
The notation with the sums $\sum$ only made life easier and typos less likely. The point is: if you take this expression modulo $17^9$ then only $x_0^9$ remains. And the same holds with different coefficients for $(x_0 + 17^9\cdot n)^3.$ This means, if $x_0=3641456693$ is a solution, then we know that
$$\begin{array}{lll} (3641456693+ 118587876497\cdot n)^9&\equiv (3641456693)^9+13\cdot (3641456693)^3 -3641456693 +100336 \\[10pt] &\equiv x_0^9+13x_0^3-x_0+100336 \equiv 0 \pmod{17^9} \end{array}$$

thank fresh_42 very much. i think i'm understanding
op question is easy

for post number 3 i can't proof all the solutions without a computer. what if this question come in the test? can i get the answer with a casio calculator?

 

[fresh_42]

thank fresh_42 very much. i think i'm understanding
op question is easy

for post number 3 i can't proof all the solutions without a computer. what if this question come in the test? can i get the answer with a casio calculator?

Tests usually do not have such complicated numbers. You would need to "guess" the solution $x_0=3641456693$ which is not very likely as long as you aren't a genius.

This is a bit different in the original question in post #1. Here we had
$$x^4-13x^3+11x-3\equiv 0\pmod{7^8}$$and a specific solution $x=-1$ can be guessed: just test small numbers like $\pm 2,\pm1,0 .$ This allows us to perform a polynomial (long) division:
$$\begin{array}{lll} (x^4-13x^3+11x-3)\, : \,(x-(-1))=x^3 - 14 x^2 + 14 x - 3 \end{array}$$and we can write
$$x^4-13x^3+11x-3=(x^3 - 14 x^2 + 14 x - 3)\cdot(x+1)\equiv 0\pmod{7^8}.$$This means that $7^8$ divides $(x^3 - 14 x^2 + 14 x - 3)\cdot(x+1)$ and thus that in particular $7$ divides $(x^3 - 14 x^2 + 14 x - 3)\cdot(x+1).$ Seven is prime and we have learned that if a prime divides a product, then it has to divide at least one of the factors.

Case 1: $7$ divides $(x^3 - 14 x^2 + 14 x - 3).$

In this case, we take the equation modulo seven and get $x^3-3\equiv 0\pmod{7}$ and in other words $x^3\equiv 3\pmod{7}.$ Possible remainders modulo $7$ are $\{0,1,2,3,4,5,6\}$ so $\{0^3,1^3,2^3,3^3,4^3,5^3,6^3\}=\{0,1,8,27,64,125,216\}\equiv \{0,1,1,6,1,6,6\} \pmod{7}$ which does not contain our remainder $3 .$ This means that this case is impossible.

Case 2: $7$ divides $x+1.$

We have just seen that $7$ does not divide $(x^3 - 14 x^2 + 14 x - 3).$ Hence all sevens must be divisors of $x+1,$ i.e. $x+1\equiv 0 \pmod{7^8}$ and $x\equiv 7^8-1= 5,764,800.$ We have already seen (by using the binomial formula) that if $x= 5,764,800$ is a solution, so will be all numbers
$$x= 5,764,800 + (7^8)\cdot n= 5,764,800+ 5,764,801\cdot n$$for any integer $n\in \mathbb{Z}.$ These are therefore all possible solutions to your original question.

And, yes, I have only used a calculator to calculate $7^8=5,764,801.$ But I guess that it would be ok in a test if you stick by $7^8$ instead of calculating it.

 

[logistic_guy]

Tests usually do not have such complicated numbers. You would need to "guess" the solution $x_0=3641456693$ which is not very likely as long as you aren't a genius.

This is a bit different in the original question in post #1. Here we had
$$x^4-13x^3+11x-3\equiv 0\pmod{7^8}$$and a specific solution $x=-1$ can be guessed: just test small numbers like $\pm 2,\pm1,0 .$ This allows us to perform a polynomial (long) division:
$$\begin{array}{lll} (x^4-13x^3+11x-3)\, : \,(x-(-1))=x^3 - 14 x^2 + 14 x - 3 \end{array}$$and we can write
$$x^4-13x^3+11x-3=(x^3 - 14 x^2 + 14 x - 3)\cdot(x+1)\equiv 0\pmod{7^8}.$$This means that $7^8$ divides $(x^3 - 14 x^2 + 14 x - 3)\cdot(x+1)$ and thus that in particular $7$ divides $(x^3 - 14 x^2 + 14 x - 3)\cdot(x+1).$ Seven is prime and we have learned that if a prime divides a product, then it has to divide at least one of the factors.

Case 1: $7$ divides $(x^3 - 14 x^2 + 14 x - 3).$

In this case, we take the equation modulo seven and get $x^3-3\equiv 0\pmod{7}$ and in other words $x^3\equiv 3\pmod{7}.$ Possible remainders modulo $7$ are $\{0,1,2,3,4,5,6\}$ so $\{0^3,1^3,2^3,3^3,4^3,5^3,6^3\}=\{0,1,8,27,64,125,216\}\equiv \{0,1,1,6,1,6,6\} \pmod{7}$ which does not contain our remainder $3 .$ This means that this case is impossible.

Case 2: $7$ divides $x+1.$

We have just seen that $7$ does not divide $(x^3 - 14 x^2 + 14 x - 3).$ Hence all sevens must be divisors of $x+1,$ i.e. $x+1\equiv 0 \pmod{7^8}$ and $x\equiv 7^8-1= 5,764,800.$ We have already seen (by using the binomial formula) that if $x= 5,764,800$ is a solution, so will be all numbers
$$x= 5,764,800 + (7^8)\cdot n= 5,764,800+ 5,764,801\cdot n$$for any integer $n\in \mathbb{Z}.$ These are therefore all possible solutions to your original question.

And, yes, I have only used a calculator to calculate $7^8=5,764,801.$ But I guess that it would be ok in a test if you stick by $7^8$ instead of calculating it.

thank fresh_42 very much

i think if difficult question come in the test, i'll cheat from the internet