Skip to main content
Mathematics

Return to Question

added 9 characters in body; edited title
Source Link
Peter Woolfitt
Peter Woolfitt
  • 21.5k
  • 6
  • 59
  • 93

Proving that 45$45$ is composite using Fermat's Little Theorem

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

If I understand, the reason that finding such a $b$ would be sufficient to show that 45$45$ is composite is because this would demonstrate the contrapositive of Fermat's Little Theorem insofar as if $a^p \not \equiv a$ (mod p)$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.

Proving that 45 is composite using Fermat's Little Theorem

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$ (mod 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$ (mod 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.

Proving that $45$ is composite using Fermat's Little Theorem

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.

Source Link
letsmakemuffinstogether
letsmakemuffinstogether
  • 1.9k
  • 2
  • 19
  • 33

Proving that 45 is composite using Fermat's Little Theorem

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$ (mod 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$ (mod 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.