Question

For fun:-
which values of n, this statement is true
\(5|n^7-4\)

Answer 1

\[n^7 \equiv 4\pmod{5}\]

Answer 2

\[n^4\cdot n^3 \equiv 4\pmod{5}\]

\[1\cdot n^3 \equiv 4\pmod{5}\]

\[ n^3 \equiv 4\pmod{5}\]

Answer 3

nice , keep going

Answer 4

take log both sides

Answer 5

\[\mathrm{ind}~ n^3 \equiv \mathrm{ind}~4 \pmod{5} \]

Answer 6

\[3~\mathrm{ind}~ n \equiv \mathrm{ind}~4 \pmod{5} \]

Answer 7

what id "ind"
:O

Answer 8

indian log

Answer 9

haha it is "log" equivalent for congruences

Answer 10

lol not kidding !

Answer 11

let me finish this problem first maybe, after that il define what it is

Answer 12

ok go ahead

Answer 13

\[3~\mathrm{ind}~ n \equiv \mathrm{ind}~4 \pmod{\phi(5)} \]


\[3~\mathrm{ind}~ n \equiv 2 \pmod {4}\]

\[\mathrm{ind}~ n \equiv 2 \pmod {4}\]

\[ n \equiv 4 \pmod 5\]

Answer 14

so all the possible solutions are \(n = 4 + 5k\) where \(k\) is any integer

Answer 15

nice !
ok now evaluate ind for me , cuz i dint got it

Answer 16

Alright, before talking about log/ind, lets do this without using this fancy stuff

Answer 17

\[n^3 \equiv 4\pmod{5}\]

we can solve this using just algebra (division algorithm)

Answer 18

every integer can be represented in one of the forms : {5k, 5k+1, 5k+2, 5k+3, 5k+4}

consider 5 cases and see which ones give you a remainder 0

Answer 19

i used mod only to solve it xD
n=0,1,2,3,4 mod 5
n^7=0,1,2,3,4 mod 5
n=4 mod 5 give the solution

Answer 20

ikr :) just wanted to show you these cool stuff

Answer 21

yeah i wanna see these cool stuff :O

Answer 22

we can discuss after exams maybe..

Answer 23

ind is similar to log

Answer 24

okkk

Answer 25

it follows all log properties :
\[a^{\text{ind}~ n} \equiv n \]
\[\text{ind} ~ n^k \equiv k~\text{ind} ~ n \]
\[\text{ind} ~ (ab) \equiv ~\text{ind} ~ (a) +\text{ind} ~ (b) \]

etc.. this is simple theory based on primitive roots. we can do more problems after exams :)

Answer 26

:O

Answer 27

google cant find ind symbol

Answer 28

i can make you understand everything about indices and primitive roots in less than 1 hour mathmath

Answer 29

oh thnks

http://math.stackexchange.com/questions/363963/how-do-you-compute-operatornameind-r-a

Answer 30

lets do it if you're interested and when you're free as i also want to understand these more

Answer 31

m free now by the way

Answer 32

Good, we will start with fermat's little theorem

Answer 33

Fermat's little theorem tells us
\[a^{p-1}\equiv 1 \pmod{p}\]

whenever \(a\) is not divisible by \(p\)

Notice that here we have \(p-1\) numbers relatively prime to \(p\) : \(\{1,2,3,...,p-1\}\)

Answer 34

yes i knoww ,ok

Answer 35

each of these numbers satisfy the fermat's little theorem, for example :
\[2^{4}\equiv 1 \pmod{5}\]

Answer 36

Also we have
\[4^{4}\equiv 1 \pmod{5}\]

Answer 37

\(\large\tt \begin{align} \color{black}{(2^{12}-1)~(\mod 13)\equiv 0\hspace{.33em}\\~\\
(2^{18}-1)~(\mod 19)\equiv 0\hspace{.33em}\\~\\
}\end{align}\)

Answer 38

im sure you knew all these, we're going to define primitive root based on this

Answer 39

yes i know feramet

Answer 40

look closely at
\[4^{4}\equiv 1 \pmod{5}\]

Answer 41

look more closely at the exponent
is \(4\) the least exponent for which aboveyields true ?

Answer 42

Nope. because we have
\[4^{\color{Red}{2}} \equiv 1 \pmod {5}\]

Answer 43

yes it works for
it works also for
\(\large\tt \begin{align} \color{black}{(4^{2}(\mod 5)\equiv 1\hspace{.33em}\\~\\

}\end{align}\)

Answer 44

yes so the exponent "4" is not least
there is another number "2" for which you also get 1, yes ?

Answer 45

yes

Answer 46

how about the powers of 2

Answer 47

\[2^4 \equiv 1 \pmod{5}\]

Answer 48

is there any power less than 4 that gives you 1 ?

Answer 49

no

Answer 50

\(2^{0}\) does gives

Answer 51

we are only considering the powers between 1 and p-1

Answer 52

powers between 1 and 4 here

Answer 53

not it doen'st give 2^1=2 (mod 5)
2^2=4 (mod 5)
2^3=3 (mod 5)

Answer 54

\(2^1 \equiv 2\)

\(2^2 \equiv 4\)

\(2^3 \equiv 8\equiv 3\)

\(2^4 \equiv 16 \equiv 1 \)

so the \(p-1\) is the least power that gives you 1 for 2

Answer 55

we say \(2\) is a primitive root of \(5\)

Answer 56

now that you have seen what a primitive root is, lets formally define it

Answer 57

2 is primitive root because below 2^4 doesnt gives \(\equiv 1\)

Answer 58

for mod 5

Answer 59

2 is primitive root because only 2^4 gives 1

Answer 60

4 is not primitive root because 4^2 also gives 1

Answer 61

we are talking about mod 5 ofcourse

Answer 62

ok i see the defn

Answer 63

Definition : \(a\) is a primitive root of \(\mod p\) if \(p-1\) is the least value that satisfies \(a^{p-1}\equiv 1 \pmod{p}\)

Answer 64

ok i get that

Answer 65

lets do 2-3 examples before moving on to indices

Answer 66

find all the primitive roots of \(\mod 5\)

Answer 67

how do i find that ?

Answer 68

2 is of cos

Answer 69

you're in mod 5, so you just need to check 5 numbers : {1, 2, 3, 4, 5}

Answer 70

3 should be

Answer 71

Right, 2 and 3 are primitive roots of 5

are there any more ?

Answer 72

no cuz 4 is a multiple of 2

Answer 73

do you mean, 4 is not a primitive root because \(4^2 \equiv 1 \pmod{5}\)

Answer 74

yes also \(4^2 \equiv 1 \pmod{5}\) is same as \(2^4 \equiv 1 \pmod{5}\)}

Answer 75

Ahh I see! thats a good observation

Answer 76

last example on primitive roots :

find all the primitive roots of 7

Answer 77

\(\large\tt \begin{align} \color{black}{2,3,5\hspace{.33em}\\~\\

}\end{align}\)

Answer 78

thats fast! how did u get them ?

Answer 79

all are prime below \(7\)

Answer 80

2 is not a primitive root of 7 because \(2^3 \equiv 1 \pmod{7}\)

Answer 81

you need to stick to the definition
it doesn't matter whether a number is prime or not

Answer 82

ok so if \(a^n \equiv 1 mod~ p\)
a is not primitive to p

Answer 83

\(a\) is not a primitive root only if that congruence is true for some \(n\) less than \(p-1\)

Answer 84

2 is not a primitive root because we have \(2^3 \equiv 1 \pmod{7}\)
and 3 is less than 6

Answer 85

how ever 3 is a primitive root because \(3^6\equiv 1 \pmod{7}\)
and there are no other powers that give you 1

Answer 86

it takes some time to get use to the definition

Answer 87

ok so \(2^4 \equiv 1 \pmod{5}\) 2 is primitive beacause \(4\not <5-1\) for \(mod ~5\)

Answer 88

2 is primitive root because there are no other powers that give you 1
4 is the least power

Answer 89

yes i see it will take time

Answer 90

here are the primitive roots for few prime mods :

```
5 : {2, 3}
7 : {3, 5}
11 : {2, 6, 7, 8}
13 : {2, 6, 7, 11}
```

Answer 91

notice 11 and 13 have four primitive roots each

Answer 92

it is true that every prime has atleast one primitive root

Answer 93

since its satisfies Fermat !

Answer 94

so there are primitive roots only for prime numbers ?

Answer 95

yesss

Answer 96

thats a good question, the answer is no. lets move to indices for now

Answer 97

lol

Answer 98

haha the answer is yes