IMO 1971 | EULER'S THEOREM

[stoic lodge]

Says pairwise coprime. Doesn't have to be coprime with all the others

Nvm oops

Actually, if $a_{k+1}$ is coprime to all $a_i$ with $1\leq i\leq k$ then it is pairwise coprime

[lone wedge]

SelahW

[vale imp]

Yes, then?

What I don't understand is why a(k+1) = 2^ϕ(a1.a2...ak) - 3 will be pairwise coprime with the previous terms of the sequence.

[stoic lodge]

It's coprime to all the previous terms because for all $a_i$, it's not 0 mod $a_i$

[lone wedge]

SelahW

[vale imp]

35 is not congruent to 0 modulo 15, but gcd(15, 35) > 1.

That is, a(k+1) being incongruent to 0 mod a(i) does not mean that gcd(a(k+1), a(i)) = 1.

[white quarry]

If phi(a_i) divides n then 2^n-3 is congruent to -2 mod a_i, so any common divisor of 2^n-3 and a_i must be also a divisor of 2. But we know that 2 and a_i are coprime. So, 2^n-3 is coprime to any a_i.

[vale imp]

"so any common divisor of 2^n-3 and a_i must be also a divisor of 2" Why? I don't understand the implication.

[white quarry]

The congruence means 2=a_i * N-(2^n-3). So if d is some common divisor of 2^n-3 and a_i then it should divide 2.