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 [imath] x=-1\equiv 5,764,800 \pmod{7^8}[/imath]?

 

[logistic_guy]

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

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. [imath]f(x) \equiv 0 \pmod{p^n} [/imath] only means that [imath] p\,|\,p^n\,|\,f(x) [/imath] from where you can start. Things quickly become complicated if you cannot factor [imath] f(x) .[/imath]

 

[Agent Smith]

[imath]y = x^4 - 13x^3 + 11x - 3[/imath]

[imath]x + 1 = 7^8[/imath]

Shooting in the dark

 

[logistic_guy]

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

thank

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

what this mean? say it in words

View attachment 38733
[imath]y = x^4 - 13x^3 + 11x - 3[/imath]

[imath]x + 1 = 7^8[/imath]

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 [imath] p [/imath] divides [imath] p^n [/imath] and [imath] p^n [/imath] divides [imath] f(x) [/imath] and so [imath] p [/imath] divides [imath] f(x). [/imath]

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 [imath] f(x)=g(x)\cdot h(x) [/imath] so that if [imath] p [/imath] divides [imath] f(x) [/imath] it means that [imath] p [/imath] divides [imath] g(x) [/imath] or [imath] p [/imath] divides [imath] h(x) [/imath] or both. That's all you can say.

Your second equation [imath] 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}[/imath] cannot be factored without using numerical approximations, so [imath] 17^9 [/imath] divides [imath] f(x) [/imath] 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
[math] f(x)\equiv 0\pmod{17^9}\Longleftrightarrow x = 118587876497 n + 3641456693 \quad( n \in \mathbb{Z}). [/math]

 

[logistic_guy]

It means that [imath] p [/imath] divides [imath] p^n [/imath] and [imath] p^n [/imath] divides [imath] f(x) [/imath] and so [imath] p [/imath] divides [imath] f(x). [/imath]

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 [imath] f(x)=g(x)\cdot h(x) [/imath] so that if [imath] p [/imath] divides [imath] f(x) [/imath] it means that [imath] p [/imath] divides [imath] g(x) [/imath] or [imath] p [/imath] divides [imath] h(x) [/imath] or both. That's all you can say.

Your second equation [imath] 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}[/imath] cannot be factored without using numerical approximations, so [imath] 17^9 [/imath] divides [imath] f(x) [/imath] 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
[math] f(x)\equiv 0\pmod{17^9}\Longleftrightarrow x = 118587876497 n + 3641456693 \quad( n \in \mathbb{Z}). [/math]

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 [imath] 17^9= 118587876497.[/imath] The number [imath] 3641456693 [/imath] is one solution, that repeats every [imath] 118587876497 [/imath] numbers again in both directions. You can test e.g. [imath] 3641456693+ 118587876497=122229333190[/imath] or [imath] 3641456693- 118587876497=-114946419804[/imath]. However, the ninth powers of them don't look nice.

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

[math]\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}[/math]This was the proof that all numbers [imath] x_0+17^9\cdot n [/imath] 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?

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

You could try distributing the eight [imath]7[/imath]s among the [imath]2[/imath] factors.

 

[logistic_guy]

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

thank

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

[math]\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}[/math]This was the proof that all numbers [imath] x_0+17^9\cdot n [/imath] 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

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

You could try distributing the eight [imath]7[/imath]s among the [imath]2[/imath] 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 [imath] 118587876497\cdot n+3641456693 [/imath] is a solution for any integer [imath] n [/imath] if [imath] 3641456693 [/imath] is a solution. I did not prove how to find [imath] 3641456693. [/imath]

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

This means that e.g.
[math]\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}[/math]
The notation with the sums [imath] \sum [/imath] only made life easier and typos less likely. The point is: if you take this expression modulo [imath] 17^9 [/imath] then only [imath] x_0^9 [/imath] remains. And the same holds with different coefficients for [imath] (x_0 + 17^9\cdot n)^3. [/imath] This means, if [imath] x_0=3641456693 [/imath] is a solution, then we know that
[math]\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}[/math]

 

[logistic_guy]

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

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

This means that e.g.
[math]\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}[/math]
The notation with the sums [imath] \sum [/imath] only made life easier and typos less likely. The point is: if you take this expression modulo [imath] 17^9 [/imath] then only [imath] x_0^9 [/imath] remains. And the same holds with different coefficients for [imath] (x_0 + 17^9\cdot n)^3. [/imath] This means, if [imath] x_0=3641456693 [/imath] is a solution, then we know that
[math]\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}[/math]

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 [imath] x_0=3641456693 [/imath] 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
[math] x^4-13x^3+11x-3\equiv 0\pmod{7^8} [/math]and a specific solution [imath] x=-1 [/imath] can be guessed: just test small numbers like [imath] \pm 2,\pm1,0 .[/imath] This allows us to perform a polynomial (long) division:
[math]\begin{array}{lll} (x^4-13x^3+11x-3)\, : \,(x-(-1))=x^3 - 14 x^2 + 14 x - 3 \end{array}[/math]and we can write
[math] x^4-13x^3+11x-3=(x^3 - 14 x^2 + 14 x - 3)\cdot(x+1)\equiv 0\pmod{7^8}. [/math]This means that [imath] 7^8 [/imath] divides [imath] (x^3 - 14 x^2 + 14 x - 3)\cdot(x+1) [/imath] and thus that in particular [imath] 7 [/imath] divides [imath] (x^3 - 14 x^2 + 14 x - 3)\cdot(x+1). [/imath] 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: [imath] 7 [/imath] divides [imath] (x^3 - 14 x^2 + 14 x - 3). [/imath]

In this case, we take the equation modulo seven and get [imath] x^3-3\equiv 0\pmod{7} [/imath] and in other words [imath] x^3\equiv 3\pmod{7}. [/imath] Possible remainders modulo [imath] 7 [/imath] are [imath] \{0,1,2,3,4,5,6\} [/imath] so [imath] \{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}[/imath] which does not contain our remainder [imath] 3 .[/imath] This means that this case is impossible.

Case 2: [imath] 7 [/imath] divides [imath] x+1. [/imath]

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

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

 

[logistic_guy]

Tests usually do not have such complicated numbers. You would need to "guess" the solution [imath] x_0=3641456693 [/imath] 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
[math] x^4-13x^3+11x-3\equiv 0\pmod{7^8} [/math]and a specific solution [imath] x=-1 [/imath] can be guessed: just test small numbers like [imath] \pm 2,\pm1,0 .[/imath] This allows us to perform a polynomial (long) division:
[math]\begin{array}{lll} (x^4-13x^3+11x-3)\, : \,(x-(-1))=x^3 - 14 x^2 + 14 x - 3 \end{array}[/math]and we can write
[math] x^4-13x^3+11x-3=(x^3 - 14 x^2 + 14 x - 3)\cdot(x+1)\equiv 0\pmod{7^8}. [/math]This means that [imath] 7^8 [/imath] divides [imath] (x^3 - 14 x^2 + 14 x - 3)\cdot(x+1) [/imath] and thus that in particular [imath] 7 [/imath] divides [imath] (x^3 - 14 x^2 + 14 x - 3)\cdot(x+1). [/imath] 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: [imath] 7 [/imath] divides [imath] (x^3 - 14 x^2 + 14 x - 3). [/imath]

In this case, we take the equation modulo seven and get [imath] x^3-3\equiv 0\pmod{7} [/imath] and in other words [imath] x^3\equiv 3\pmod{7}. [/imath] Possible remainders modulo [imath] 7 [/imath] are [imath] \{0,1,2,3,4,5,6\} [/imath] so [imath] \{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}[/imath] which does not contain our remainder [imath] 3 .[/imath] This means that this case is impossible.

Case 2: [imath] 7 [/imath] divides [imath] x+1. [/imath]

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

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

thank fresh_42 very much

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