1

I'm familiar with Fermat's Little Theorem and Euler's Totient, but I'm wondering whether the fact that the only shared factor of $(a,N)=1$ has something to do with the fact that, given the prior constraints there exists at least one $x$ (with $x$ being one of elements of the least non-zero positive remainder class of $N$) where $a^x \equiv 1 \pmod{N}$?

It doesn't appear to be dependent upon the modulus being prime since using a modulus of 10 the following is true:

$9^1\pod{10}=9$
$9^2\pod{10}=1$
$9^3\pod{10}=9$
$9^4\pod{10}=1$
$9^5\pod{10}=9$
$9^6\pod{10}=1$
$9^7\pod{10}=9$
$9^8\pod{10}=1$
$9^9\pod{10}=9$

This is also really naive but another observation is that given the previous assumptions the initial base will always be less than $N$ and $a^1 \pmod{N}$ will always return $a$, so given $\gcd(a,N)=1$, $a$ will always produce at least one remainder other than $1$.

I know there's some intuition that I'm missing?

Bernard
  • 175,478
JohnGalt
  • 189

3 Answers3

2

Consider all powers $a^r\bmod N$ for $r=1,2,3,\ldots$ There are an infinite number of them, but they can only take values $0\le a^r\bmod N\le N-1$. So sooner or later we must encounter a repeated value; say $a^s\equiv a^t\bmod N$, for some $s<t$.

Now, since $\gcd(a,N)=1$, we know that $\gcd(a^s,N)=1$. So we can divide by $a^s$, and we get $1\equiv a^{t-s}\bmod N$. Which is what we wanted.

TonyK
  • 64,559
  • 1
    Apologize for the probable stupidity of this observation, but let's take $N=10$ and a base $a=4$, the $gcd(4,10)=2$ and yet given the least non-zero remainder class there is no $x$, in $a^x \pmod{10}$ equal to $2$. I know I'm probably comparing apples to oranges but I was looking for something like that to show why being co-prime was important. – JohnGalt Jul 03 '19 at 20:03
  • 1
    @JohnGalt: You were right to pull me up on that! It's not enough for $a^s$ to be non-zero $\bmod N$, we also need $\gcd(a^s,N)=1$ if we want to divide by it. I have corrected my answer. – TonyK Jul 03 '19 at 20:18
1

It is because for a number to have an inverse (i.e. some element which product of both is a residue of $1$), we need the number to be relatively prime with the modulus.

$$a \cdot a^{x -1} \equiv_N 1$$

We have an inverse of $a$ in this case. You see now?

§ Further Explanation §

$$ax + Ny = 1$$

So $x$ modulo $n$ is the inverse but by Bezout's theorem this is only true if $a$ and $N$ are relatively prime.

İbrahim İpek
  • 1,126
  • The two $x$'s need not be the same. – Anurag A Jul 03 '19 at 19:46
  • Author asks about why we need both to be relatively prime for these theorems to be true – İbrahim İpek Jul 03 '19 at 19:49
  • I'm relatively new to Number Theory and sometimes things are true axiomatically and some things are true based upon some other foundation. For example, I stated "given gcd(,)=1, will always produce at least one remainder other than 1". I could say that it's true because "given the previous assumptions the initial base will always be less than and 1(mod) will always return ". I'm trying to determine if there's a why to my initial question or is it just true on its face? Or true because of Bezout's theorem (which I don't know but will research)? – JohnGalt Jul 03 '19 at 19:55
  • 1
    If you need some further help, i can teach you number theory and explain some hard to comprehend concepts. Possibly on a discord server? – İbrahim İpek Jul 03 '19 at 21:05
1

Not sure this fully answers you question (not very clear to me), but $\gcd(a,N)=1$ implies $a$ is a unit modulo $N$, so the congruence class of $a\bmod N$ generates a finite group, and it has a power congruent to $1$. One may add that this group is a subgroup of the (multiplicative) group $U_N$ of units modulo $N$, and by Lagrange's theorem, it has order a divisor of $$|U_N|=\varphi(N).$$ For your example, $\;\varphi(10)=\varphi(2)\,\varphi(5)=4$.

Bernard
  • 175,478
  • In this context, what does "unit" mean $\pmod{N}$? – JohnGalt Jul 03 '19 at 20:05
  • 1
    It simply means there exists $b$ such that $ab\equiv 1\mod N$. The set of congruence classes is a commutative ring with $1$ (denoted $\mathbf Z/N\mathbf Z)$. – Bernard Jul 03 '19 at 20:10