0
$\begingroup$

Let's consider two number $a$ and $b$ such as $gcd(a,b)=1$. Can you explain me intuitively why there exist $n>0$ such as $a^{n} \equiv 1 \space (mod \space b)$ ?

$\endgroup$
4
  • 1
    $\begingroup$ If you start looking at powers of $a$ you'd eventually start getting repeats when considering the result modulo $b$, say $a^x$ and $a^{x+y}$ both resulting in $z\pmod{b}$, but then $a^xa^y\equiv a^x\equiv z\pmod{b}$. Try to reason that $a^y\equiv 1\pmod{b}$, using the fact that $a$ is coprime to $b$ and so $z$ is as well. $\endgroup$
    – JMoravitz
    Commented May 22, 2019 at 13:21
  • $\begingroup$ At this point, can we infere that $y<b$ ? If yes how ? $\endgroup$
    – AleWolf
    Commented May 22, 2019 at 13:30
  • 1
    $\begingroup$ Why should we care that $y<b$? From what I wrote alone, no you cannot, but you can add a few additional conditions... changing the opening statement to "If you start looking at the first $b$ powers of $a$ you'd eventually start getting repeats..." We know that we'll get repeats because of the pigeon-hole principle, us having at most $b-1$ holes (since it is impossible for $a^x \equiv 0\pmod{b}$) and having $b$ pigeons. This guarantees that $1\leq x<x+y\leq b$ and so $1\leq y\leq b-x<b$ $\endgroup$
    – JMoravitz
    Commented May 22, 2019 at 13:34
  • $\begingroup$ Thanks so much, if you post i vote your answer as the correct one $\endgroup$
    – AleWolf
    Commented May 22, 2019 at 13:47

1 Answer 1

1
$\begingroup$

Sure:

  • Exponents don't cause a change in gcd.
  • There are finitely many remainders possible.
  • There are, therefore, repeated remainders are forced after a certain point.

A proof of Fermat's little theorem I once saw is as follows:

Let A, be the set of all products of a, and one of the natural numbers less than b (b in this case is prime, and $\gcd(a,b)=1$). Any of these giving same remainder on division by b, implies that the two natural numbers a was multiplied by, are congruent mod b. This of course is impossible.

The product of all elements of set A, is: $$a^{b-1}(b-1)!$$ and the set of all non-zero remainders is forced to occur in this set by the above argument, so $$a^{b-1}(b-1)!\equiv (b-1)!\bmod b$$ which turns into:$$a^{b-1}\equiv 1\bmod b$$ when you cancel the factor of factorial on both sides.

It then follows using $$1^r=1$$ and it's equivalent in modulo that all multiples of $b-1$ , as exponents are 1 mod b . These combine in the composite cases.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .