From Fermat's to Brilliant

Number Theory Level 3

Let $x$ be a prime number larger than 3. What is the probability that $x|2^{x-1} - 1$ and $x | 3^{x-1} - 1$ ?

\frac14

0

\frac12

1

2 solutions

Sam Bealing
Jun 12, 2016

Fermat's Little Theorem gives for all primes $p$ :

$a^{p-1} \equiv 1 \pmod{p} \implies a^{p-1} -1 \equiv 0 \pmod{p} \implies p \vert a^{p-1}$

The condition is that $a$ and $p$ are comprime but because $p>3$ it follows $gcd(p,2)=gcd(p,3)=1$ so:

$p \vert 2^{p-1}-1 \quad p \vert 3^{p-1}-1$

This applies to all $p$ so the probability is:

$\color{#20A900}{\boxed{\boxed{1}}}$

Moderator note:

Simple standard approach.

Even if the problem has not stated "prime larger than 3", the probability still would have been 1.

Mateo Matijasevick - 5 years ago

@achal jain I do not like using probability, because there is no uniform distribution on countably infinite terms. That makes it trickier to rigorously express what you mean.

Calvin Lin Staff - 4 years, 12 months ago

Thanks for your feedback. Your are right , Will take care of it next time.

Achal Jain - 4 years, 12 months ago

Sumukh Bansal
Nov 9, 2017

According to Fermat's Little Theorem all prime numbers $p$ : $a^{p-1} \equiv 1 \pmod{p} \implies a^{p-1} -1 \equiv 0 \pmod{p} \implies p \vert a^{p-1}$ The equations satisfy the above equations.So, the probability is $\color{#3D99F6}{\boxed{1}}$

From Fermat's to Brilliant

2 solutions

Moderator note:

0 pending reports