Question

\(\large \begin{align} \color{black}{

\normalsize \text{prove\show that the equation has no solution over integers} \hspace{.33em}\\~\\
(x^3 + 7 y^2 + 5)=0 \hspace{.33em}\\~\\
}\end{align}\)

Answer 1

\(\large\begin{align} \color{black}{
\normalsize \text{one method is the } \pmod{7} \hspace{.33em}\\~\\

\normalsize \text{i would like to know if their are other methods as well .}\hspace{.33em}\\~\\
}\end{align}\)

Answer 2

we can prove a much stronger statement :
\[\large x^3 + 7y^{n} + 5 = 0\]

has no solutions over intgers \(x, y\) and whole number \(n\)

Answer 3

yes beacause that goes way with 7 ?

Answer 4

\(y^n\)

Answer 5

Yes.. below is the most simplified form that the question can be framed :

Prove that \(a^3+5\) is not divisible by 7 for all integers \(a\)

Answer 6

show me your solution xD

Answer 7

\((1)^3 \equiv1 \pmod{7}
\\
(2)^3 \equiv1 \pmod{7}\\
(3)^3 \equiv6 \pmod{7}\\
(4)^3 \equiv1 \pmod{7}\\
5^3 \equiv6 \pmod{7}\\
6^3 \equiv 6 \pmod{7}\\

\)

Answer 8

that works because 7 is small! how do we prove below :
\(\large a^3 + 5 \) is not diviisble by 43 for all integers \(a\) :P

Answer 9

oh let me think

Answer 10

mod 43 works, the solution will be lengthy thats all

Answer 11

how did u worked out \(43 \)?

Answer 12

You want to show \(a^3+5\) is not divisible by \(43\) for all integers \(a\)

simply consider 43 cases for \(a\) : {43k, 43k+1, ..., 43k+42}

Answer 13

ohk i get that

Answer 14

but that too lengthy

Answer 15

By binomial theorem \((43k+l)^3 = 43X + l^3 \equiv l^3 \pmod{43}\)

Answer 16

Yeah, that method is called division algorithm
you can prove almost ALL divisibility problems using that method, but as you can see the proof is very boring..

Answer 17

does the primitive root can be used to quickly work out \(mod ~43\)

Answer 18

if not that seems to be programming question

Answer 19

it can be done in one line using primitive roots if you have a table for indices of any primitive root of 43

Answer 20

start by finding out a primitive root of 43

Answer 21

3,5,12,18 are one of those

Answer 22

yes, lets use 3 as base of our logarithm as it is the smallest number.. so it will be easy to work out powers..

Answer 23

if we use 3 soo we not need to use other primitive roots of 43 ?

Answer 24

one primitive root is enough..

Answer 25

oh that cool!

Answer 26

we want to show below congruence has no solutions :
\[a^3+5 \equiv 0 \pmod{43}\]

Answer 27

we take log both sides

Answer 28

which is same as

\[a^3 \equiv -5 \pmod{43}\]

Answer 29

which is same as

\[a^3 \equiv 38 \pmod{43}\]

yes now take log base 3 both sides

Answer 30

\(\large\begin{align} \color{black}{
3ind~a \equiv ind 38 \pmod{43}\hspace{.33em}\\~\\
}\end{align}\)

Answer 31

since this is a special logarithm, we use a different notation : \(\text{ind}_3\)

Answer 32

looks good!

Answer 33

lets pause a bit for few minutes

Answer 34

ok

Answer 35

yes wait

Answer 36

sorry not that, one sec..

Answer 37

u said thar it should be \(p-1\)so \(43-1=42\)

Answer 38

Exactly! we should end up with below congruence to solve :
\[\large 3\text{ind}_3\ a \equiv \text{ind}_3 38 \pmod{\color{Red}{42}}\]

Answer 39

our goal is to prove that above congruence has no solutions

thats same as proving that the congrunce \(a^3 = 38 \pmod {43}\) has no solutions because we have just taken log both sides..

Answer 40

lets pause a bit now and see how to solve linear congruences in general

Answer 41

do you know how to solve below congrunce :
\[3x \equiv 22 \pmod{42}\]

?

Answer 42

wait let me see

Answer 43

trial and error is a pain
there is really a neat way to work this..

Answer 44

do i have to put all no upto \(41\) for \(x\)

Answer 45

yes that works, but lets see if we can work it without doing all that work..

Answer 46

\[3x \equiv 22 \pmod{42}\]

is same as

\[3x = 42k + 22\]
for all integers \(k\), yes ?

Answer 47

yes

Answer 48

\[3x = 42k+22\]
\[3x -42k=22\]
\[3(x -14k)=22\]

why does this equation makes no sense ?

Answer 49

may be it has no solution

Answer 50

yes, why ?

Answer 51

the 3 should cancel out i think

Answer 52

\[3(x -14k)=22\]

this equation is saying \(3\) times some integer equals \(22\)
which is not possible. so the congrunce \(3x\equiv 22 \pmod{42}\) has NO SOLUTIONS.

Answer 53

so is hypithesis of cancelling out 3 for integers right ?

Answer 54

*hypothesis

Answer 55

3*t = 22

can you find an integer "t" that satisfies above equaiton ?

Answer 56

lol no3*7=21,3*8=24

Answer 57

\[3(x -14k)=22\]

has no solutions in integers for the same reason

Answer 58

ok

Answer 59

because 3 is not a factor of 22

Answer 60

as simple as that ^

Answer 61

so the indices not solvable

Answer 62

Yes!

Answer 63

oh

Answer 64

\[\large 3\text{ind}_3\ a \equiv \text{ind}_3 38 \pmod{\color{Red}{42}}\]

Answer 65

if you prepare the indices table, you will see that \(\text{ind}_3 38 = 22\)

Answer 66

so tha'ts why it has no solution ?

Answer 67

so the congruence becomes

\[\large 3\text{ind}_3\ a \equiv 22\pmod{\color{Red}{42}}\]

Answer 68

ok

Answer 69

we have just worked that this congruence has NO solutions

Answer 70

it will take some time to get use to these logarithms and congruences..
i see you're very good with congruence equaitons :)

Answer 71

for integers

Answer 72

\[\large 3\text{ind}_3\ a \equiv 22\pmod{\color{Red}{42}}\]

has no solution shows that \(a^3 + 5\) is not divisible by 43

Answer 73

sry this one \(a^2+5 \pmod {43})\)

Answer 74

yes

Answer 75

ohk thats not long :)

Answer 76

than division algo

Answer 77

yes its not long because we have used the indices table : \(\text{ind}_3 38 = 22\)

working it manually might take some time :P

Answer 78

let me put the complete solution in one reply

Answer 79

Prove \(a^3+5\) is not divisible by \(43\) for all integers \(a\)

Proof :
\[a^3 \equiv -5 \pmod{43}\]
\[a^3 \equiv 38 \pmod{43}\]

take log base 3 both sides
\[3\text{ind}_3a \equiv \text{ind}_3 38 \pmod{42}\]

but we know from indices table that \(\text{ind}_3 38 = 4\) :
http://www.wolframalpha.com/input/?i=3%5E4+mod+43

so the congrunce becomes
\[3\text{ind}_3a \equiv 4 \pmod{42}\]

which is same as
\[3\text{ind}_3a = 42k+ 4\]

which is same as
\[3(\text{ind}_3a -14k) = 4\]

which is impossible because 3 is not a factor of 4.

Answer 80

\(ind_3 38 \pmod {42}\)
=\(3^x \mod 43\)

Answer 81

indices are exactly same as logarithms

Answer 82

\(\log_3 81 = 4\) because \(81 = 3^4\)

\(\text{ind}_3 38 = 4\) because \(38\equiv 3^4 \pmod{43}\)

Answer 83

so if i need to find \(ind_3 38 \pmod {42}\)

then i need to find this ?

\(3^x \pmod {43}=38\)

Answer 84

tell me how would you find below :
\[\log_2 1024\]

?

Answer 85

\(1024=2^{10}\)

Answer 86

so its \(10\) ?

Answer 87

yes, but how do you know 1024 = 2^10 ?

Answer 88

may be you worked out all the powers up to 10 ?

Answer 89

that is intuition !

Answer 90

2^1 = 2
2^2 = 4
2^3 = 8
...
2^10 = 1024

so \(\large \log_2 1024 = 10\)

Answer 91

similarly lets work out \(\large \text{ind}_3 38\) in modulo \(43\)

Answer 92

you want to solve below :
\[38 \equiv 3^x \pmod{43}\]

Answer 93

x = 4 works because 3^4 = 81
and 38 - 81 = -43 which is divisible by 43

Answer 94

ok that seems cool

Answer 95

that means \(38 \equiv 3^4 \pmod{43}\)

so \(\text{ind}_3 38 = 4\)

Answer 96

this whole stuff is cool

Answer 97

i just want you know that this is an undergraduate course and students sepnd 1 full semister on these... so you should be proud of yourself for making sense of these in just couple of hours... :)

Answer 98

O: :O