Question

[[closed]]

Answer 1

Are you using Burton ?

Answer 2

Yes !

Answer 3

I like that book

Answer 4

tell me what is a pseudo prime ?

Answer 5

n is a pseudo prime if n|2^{n}-2

Answer 6

or rather n|a^{n}-a

Answer 7

right, what is an absolute pseudo prime ?

Answer 8

\[\large a^n \equiv a \pmod{n}\]

A composite number \(n\) is called an absolute pseudo prime only if above congruence holds for all integers \(a\)

Answer 9

btw are you familiar wid congruences ?

Answer 10

yes !

Answer 11

good, lets look at what a `square free integer` means first

Answer 12

a integer which is not divided by a perfect square ???

Answer 13

thats right, another easy way to make sense of it is by looking at the prime factorization :

\(\large 30 = 2*3*5 \) is a square free integer because it is a product of single primes

Answer 14

\(\large 120 = 2^3*3*5\) is not a square free integer because the exponent of \(2\) is not \(1\)

Answer 15

In short : an integer is square free if all the exponents of primes in its prime factorization are \(1\)

Answer 16

okay! got this. I have a doubt in paragraph. it was taken that a=k and the rest follows that k^n cong k(mod n) but for the later part I am confused. Like it is written k cong k^n cong 0 modk^2. I mean how can i infer this from the last statement. Help me ! May be I am missing anything.

Answer 17

You're interpreting it correctly... let me see if I can make it more simpler for you :)

Answer 18

suppose \(n\) is an absolute pseudo prime and not square free.

since \(n\) is not square free, we have \(k^2 | n\) for some square factor, yes ?

Answer 19

yes.. !! :)

Answer 20

next, since \(n\) is an absolute pseudo prime, we have :
\[k^n\equiv k \pmod{n}\]

yes ?

Answer 21

that just another way of saying \(\large n | (k^n-k)\)

Answer 22

yes

Answer 23

we also have \(k^2 | n\)

that implies \(k^2 | (k^n-k)\)

yes ?

Answer 24

yes :)

Answer 25

\(\large k^2 | (k^n-k)\) is impossible, why ?

Answer 26

cause square of a number cannot divide the number .

Answer 27

like 25 doesnot divide 5

Answer 28

yes but we don't have \(k^2|k\)

all we have is \(k^2 | (k^n-k)\)

Answer 29

may i know why are you ignoring \(k^n\) ?

Answer 30

oho... I missed that.

Answer 31

Easy, we already know that \(k^2 | k^n\)

so \(k^2 | (k^n - k)\) is equivalent to \(k^2 | (0-k)\) whis is equivalent to \(k^2|-k\) which is equivalent to \(k^2|k\) which is nonsense.

Answer 32

we reached that because we have wrongly assumed that the absolute pseudo prime \(n\) is not square free. so the opposite of our assumption must be true : \(n\) is square free

Answer 33

one more thing for carmichael no. it is required that gcd of the the base and the composite no. to be 1 ???

Answer 34

"carmichael number" is a synonym for "absolute pseudo prime"

Answer 35

both are same

Answer 36

oh it is in the book itself, hahahahha... silly me.. anyways thank you....

Answer 37

yw:)