Question

[[answered]]

Answer 1

I am getting confused with the statement that from divisibility hypothesis pi-1|n-1. May be I am missing something in the understanding it. Please help me

Answer 2

@Kainui @ganeshie8

Answer 3

@ganeshie8

Answer 4

Explain what you think the problem is saying and talking about to the best of your ability and I'll see what I can do to help you understand it. =)

Answer 5

okay ! pi is a prime hence by the fermat theorem it can be stated that a^{pi-1} cong 1(modPi).

After that I am getting confused with the fact

if I consider n to be a pseudoprime then i can state that a^n cong a mod n.

But this is what i need to prove right.

Answer 6

It is written that pi-1|n-1 which can be written after I establish a^n cong a mod n. right ????

Answer 7

I'm a little unfamiliar with the terminology here, what does it mean to be an absolute pseudoprime?

Answer 8

absolute pseudo primes are "composite numbers" that satisfy the converse of Fermat's little theorem

Answer 9

a composite number \(n\) is called an absolute pseudo prme if \(n|(a^n-a)\) for all integers \(a\)

Answer 10

This is really fascinating, so these are the composite numbers that appear to be prime but aren't, I like that.

Answer 11

Exactly! they are the reason for failure of converse of Fermat's little thm to hold..

Answer 12

I think I might see your problem @praxer The proof is saying a is an integer that is relatively prime to n, so it must also be relatively prime to all its factors which is what you got so far. Applying Fermat's lil theorem we have that \[\large p_i | a^{p_i-1}-1\] which is not surprising at all, all primes satisfy this.

Now here is where our actual theorem proof begins. Since we are saying this implication, so we begin with this as our starting point. \[\Large p_i-1|n-1 \implies \text{n is absolute pseudoprime}\] So we're not proving that pi-1 divides n-1, we're saying given this it implies this. Does that help/make sense or did I not really answer your question?

Answer 13

Fermat little thm gives you \[a^{p_i-1}\equiv 1 \pmod{p_i}\]

rise both sides to \(k\)th power

\[a^{k(p_i-1)}\equiv 1^k \pmod{p_i}\]

which is same as
\[a^{k(p_i-1)}\equiv 1 \pmod{p_i}\]

as you can see Fermat's little thm implies \(p_i | (a^{k(p_i-1)}-1)\)

Answer 14

okay !

Answer 15

I don't know what @ganeshie put, so I'll just post what I have written so far maybe it will help to see another perspective too.

So looking at \[\large p_i-1 | n-1\] My instinct here is to take it a step out of abstraction and make a concrete example. pi-1 divides n-1 so n-1 has to either be equal or larger and a multiple o p-1. A simple way we can write this is for a positive integer k, \[\Large k(p_i-1)=n-1\] Since we already know \[\Large \gcd(a,p_i)=1 \implies \gcd (a^k,p_i)=1\] So we can apply Fermat's theorem to this: \[\Large p_i | a^{k(p_i-1)}-1 \\ \Large p_i | a^{(n-1)}-1\]

Answer 16

since \(p_i-1 | n-1\) we have \(n-1 = k(p_1-1)\) for some integer \(k\)

It follows \[a^{n-1}\equiv 1 \pmod{p_i}\]

Answer 17

multiply \(a\) both sides
\[a^{n}\equiv a \pmod{p_i}\]

Answer 18

rest is bit easy, see if you see why each individual \(p_i\) divides \(a^n-a\)..

Answer 19

okay got it. Thank you @Kainui @ganeshie8. ...

Answer 20

if you have time, maybe lets go through a quick example and see why this thm works

Answer 21

Yeah, I'm curious to see how 561 is a Carmichael number

Answer 22

Ahh thats a good number :) but lets see if it is square free as all absolute pseudo primes need to be square free

Answer 23

3*7*11 I'm cheating a little haha.

Answer 24

\[561 = 3\times 7\times 11\]

so yes this is a good candidate for absolute pseudo prime

Answer 25

TYPO. let me fix it quick :)
To show \(\color{Red}{561}\) is a Carmichael number, we need to show for all integers \(a\) such that \(\gcd(a,561)=1\), below holds :

\[a^{560}\equiv 1 \pmod{561} \]

Answer 26

Once we establish above, we can simply multiply \(a\) both sides and have
\[a^{561}\equiv a \pmod{561}\]

Answer 27

\[a^{560}\equiv 1 \pmod{561} \]

is equivalent to the system of baby congruences :
\[a^{560}\equiv 1 \pmod{3} \\a^{560}\equiv 1 \pmod{7} \\a^{560}\equiv 1 \pmod{11} \\\]

Answer 28

Alright this is is the chinese remainder theorem right?

Answer 29

The work reduces to showing below congruences are true for all \(a\) relatively prime to \(561 =3\cdot 7\cdot 11\)
\[a^{560}\equiv 1 \pmod{3} \\a^{560}\equiv 1 \pmod{7} \\a^{560}\equiv 1 \pmod{11} \\\]

Answer 30

It is easy, lets show first congruence is true :

from fermat's little thm we have \(a^2 \equiv 1 \pmod 3\)
rise both sides to 280 power : \((a^2)^{280}\equiv a^{560}\equiv 1 \pmod{3}\)

Answer 31

similarly we can show other two congruences also hold using fermat's little thm

Answer 32

you must have noticed, we need \((3-1) | (561-1)\) to conclude the baby congruence is true by using Fermat's little thm.

Answer 33

So as an example,
\(a^{10} \equiv 1 \pmod{11} \)
\((a^{11})^{186}\equiv a^{560}\equiv 1 \pmod{11}\)

And I see how what you've written is p-1 | n-1 from the problem earlier. I still need to think about this problem a little further since it seems a little off to me somehow. I think I just don't have an intuitive grasp of why the Fermat Little Theorem is true, I am just applying a memorized rule.

Answer 34

you mean
\(a^{10} \equiv 1 \pmod{11}\)
\((a^{10})^{\color{Red}{56}} \equiv a^{560}\equiv 1 \pmod{11}\)

right ?

Answer 35

Well after this first step I just multiplied both sides by a, and then raised it to the 51 power, whoops.
\(a^{10} \equiv 1 \pmod{11} \)
\(a^{11} \equiv a \pmod{11} \)
\((a^{11})^{51}\equiv a^{561}\equiv 1 \pmod{11}\)

But I guess I am missing the point here with something since I feel like what you did was somehow different but I'm not sure how.

Answer 36

Ohk.. rising \(1\) to some power is easier than rising \(a\) to power because \(1^{56} = 1\)

\(a^{10}\equiv 1 \pmod {11}\)

it is good to rise both sides to 56 power before multiplying \(a\) both sides...

Answer 37

we can multiply \(a\) first also.. it doesn't matter much yeah..

Answer 38

\(a^{10}\equiv 1 \pmod{11}\)

rise both sides to power 56
\((a^{10})^{56}\equiv 1^{56} \pmod{11}\)

which is same as
\(a^{560}\equiv 1 \pmod{11}\)

now we can multiply \(a\) both sides if we want...

Answer 39

Wait, so just to be clear is this just an issue of it being easier to see how to multiply by 10 as opposed to how I just happened to think I should add 1 since 11 is a factor of 561, or is there some other difference I should be aware of?

Answer 40

I sort of just don't get modular arithmetic honestly haha, I don't know why it makes almost no sense to me, including the Chinese Remainder theorem. There's just something off about this subject sorry haha

Answer 41

No, i see what you mean now :) lets look at your congruences :
http://gyazo.com/f818281516fd49d054d46ec9ffa8329a

Answer 42

second congruence follows from first congrunce as you're simply multiplying \(a\) both sides


but the third congruence is off

Answer 43

\(a^{11} \equiv a \pmod{11}\)


I see you're rising both sides to \(51\) power, then you shoudl get :

\((a^{11})^{51} \equiv a^{\color{Red}{51}} \pmod{11}\)

Answer 44

right ?

Answer 45

Ahhh you're absolutely right, I see haha

Answer 46

we don't know what \(a^{51}\) reduces to, so thats the reason "1" is good to have on right hand side compared to "a"

Answer 47

i think thats also the main reason why fermat's little theorem shows up in many number theory proofs..

Answer 48

Yes, this makes perfect sense to me now. So I guess why are we bothering raising this to a specific power in the first place? Once we see this:
\(a^{10} \equiv 1 \pmod{11} \)

It seems like the argument is essentially over since this can be raised to any arbitrary power.

Answer 49

Exactly!

Answer 50

ofcourse you meant "any arbitrary integer power"

Answer 51

Yeah, but how come we made it look "nice" like this?
\(a^{561} \equiv a \pmod{11} \)

Answer 52

Fermat gives
\(a^{10}\equiv 1 \pmod{11}\)

rising to 56 power gives
\(a^{560}\equiv 1 \pmod{11}\)

multilying \(a\) both sides gives
\(a^{561}\equiv a \pmod{11}\)

Answer 53

I guess I'm sort of lost, why are we doing this?

Answer 54

we want to show \(a^{561}\equiv a \pmod{561}\)

Answer 55

http://gyazo.com/22bcd33b8693843149dce941eede0cfc

Answer 56

So showing that
\(a^{561}\equiv a \pmod{3}\)
\(a^{561}\equiv a \pmod{11}\)
\(a^{561}\equiv a \pmod{17}\)
are all true implies that
\(a^{561}\equiv a \pmod{561}\)

Is this essentially what the chinese remainder theorem lets us do?

Answer 57

Yes, but chinese remainder thm is not really needed here since 3, 11, 17 are all primes

Answer 58

x = a mod p1
x = a mod p2
x = a mod p3

means all distinct primes p1, p2, p3 divide (x-a)
so their product p1*p2*p3 also divides (x-a)

Answer 59

for example

14 = 4 mod 2
14 = 4 mod 5

so we have 14 = 4 (mod 2*5)

Answer 60

I think I see what you mean, but it is a fragile bit of knowledge that I will probably forget tomorrow for some reason it isn't very sturdy to me, I'll have to think about this for a while I guess.

Answer 61

we can say this in general :
If \(a|c\) and \(b|c\) with \(\gcd(a,b)=1\), then \(ab|c\)

Answer 62

So if a=b in a bunch of different modular arithmetic systems? (residue classes? systems? rings? idk) then a=b in the product of all those multiplied together?

Answer 63

Exactly! consider another example

2 | 6
3 | 6

here gcd(2,3) = 1, so we have 2*3|6

Answer 64

I think I understand what you're saying, but how do you think about it? How does your intuition activate to say, "This might be useful to consider" Like when are some times that you used this reasoning aside from this problem here?

Answer 65

So since 2 and 3 are relatively prime, they will satisfy fermat's little theorem which is basically saying their LCM is their product?

Answer 66

This is a consequence of euclid gcd algorithm and the fact that gcd can be represented as a linear combination : \(\gcd(a,b) = ax+by\) for some integers \(x\) and \(y\)

Answer 67

I think your interpretation is right Kai

Answer 68

Ok, like for instance, looking at this picture of the number line we have this repeating unit where 2 and 3 are prime but after that this repeating symmetrical unit will always have composite numbers at the circles if I move it down, is this sort of like what mods are talking about?