2
$\begingroup$

I am trying to prove that $45$ is composite using Fermat's Little Theorem. I am given a hint which states: "Find an integer $b$ such that $b^{45} \not \equiv b \pmod{45}$ and explain why this implies that $45$ cannot be prime."

If I understand, the reason that finding such a $b$ would be sufficient to show that $45$ is composite is because this would demonstrate the contrapositive of Fermat's Little Theorem insofar as if $a^p \not \equiv a\pmod{p}$ then $p$ is not a prime.

I have first tried finding such a $b$ but I'm simply guessing and that doesn't seem like the best approach to this. Any help would be appreciated on how to proceed.

$\endgroup$
5
$\begingroup$

Well, to find a satisfactory $b$, we can make use of our knowledge of the decomposition $45=3^2\times 5$.

This means if we pick $b=3\times5=15$, then we would have $b^n\equiv0\pmod{45}$ for any $n\ge 2$ (in particular for $n=45$).

[Added for clarity]

More explicitly, note that $15^2=3^2\times5^2=45\times 5$. Hence if $n\ge2$, then $$15^n\equiv 15^2\times15^{n-2}\equiv 45\times 5\times 15^{n-2}\equiv 0\pmod {45}$$

Perhaps making use of the known factorization is in some sense cheating. In that case, you can just say $15^2=225=5\times 45$, and so $15^2\equiv 0\pmod{45}$, and then use $$15^n\equiv 15^2\times15^{n-2}\equiv 0\times15^{n-2}\equiv0\pmod{45}$$

However, our motivation for looking at the number $15$ does come from us already knowing the factorization of $45$.

$\endgroup$
  • $\begingroup$ Thank you for the response however I don't think I understand how we know that $b = 15$ will be congruent to zero for all natural-number-powers of $b$. Could you please explain that in more detail? $\endgroup$ – letsmakemuffinstogether Jun 11 '15 at 7:30
  • 1
    $\begingroup$ @letsmakemuffinstogether I've filled out my post. Does this make sense to you? $\endgroup$ – Peter Woolfitt Jun 11 '15 at 7:38
  • $\begingroup$ Clear as day. Thank you. $\endgroup$ – letsmakemuffinstogether Jun 11 '15 at 7:49
  • $\begingroup$ @lets It is the nonsquarefree character of the modulus that makes it fail - see my answer, which explains how to view it form a more general perspective. $\endgroup$ – Bill Dubuque Jun 11 '15 at 16:18
  • $\begingroup$ @Downvoter mind explaining? $\endgroup$ – Peter Woolfitt Sep 4 '15 at 13:46
1
$\begingroup$

Hint $\,\ 3^2\mid 45\mid 3^{45}\!-\!3\,\Rightarrow\, 3^2\mid 3,\,$ contradiction.


Remark $\ $ The above show that the modulus $\,n\,$ must be $\,\rm\color{#0a0}{squarefree}.\,$ It's an easy part of

Theorem $ $ (Korselt's Carmichael Criterion) $\ $ For $\rm\:1 < e,n\in \Bbb N\:$ we have

$$\rm \forall\, b\in\Bbb Z\!:\ n\mid b^e\!-b\ \iff\ n\ \ is\ \ \color{#0a0}{squarefree},\ \ and \ \ \color{#c00}{p\!-\!1\mid e\!-\!1}\ \, for\ all \ primes\ \ p\mid n\quad $$

Proof $\ $ See this answer.

$\endgroup$
1
$\begingroup$

Actually, guessing is a perfectly sensible thing to try for a problem like this. In general, for most (but not all!) composite numbers $n$, $b^n\not\equiv b$ mod $n$ for most (but again not all) numbers $b$. In particular, it makes sense to just try a small number, like $b=2$, and see what happens. The trick is to organize the calculation so as to minimize the amount of arithmetic that needs to be done. In this case, one path that works (using $45\cdot3=135$) is

$$\begin{align} 2^7&=128\equiv-7\\ 2^{14}&\equiv(-7)^2=49\equiv4\\ 2^{42}&\equiv4^3=64\equiv19\\ 2^{45}&\equiv8\cdot19=152\equiv17\not\equiv2 \end{align}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.