I'm a bit confused about the nature of one of my homework problems. It is requesting an explanation for why a congruence holds for $a^n \equiv a \;(\!\!\!\mod n)$ for a composite $n$, however this congruence is not always true from my understanding as having $a^n \not\equiv a \;(\!\!\!\mod n)$ provides that $n$ is not prime in the case that this occurs so the equivalence may not always be true. The question is however prefaced by the given $n$ being a Carmichael number though. Could anyone hint at how I should approach this explanation?  The Problem  The number 561 factors as $3 \cdot 11 \cdot 17$. First use Fermat's little theorem to prove that \begin{equation*} a^{561} \equiv a \;(\!\!\!\mod{3}), \quad  a^{561} \equiv a \;(\!\!\!\mod{11}), \quad  a^{561} \equiv a \;(\!\!\!\mod{17}) \end{equation*} for every value of $a$. Then explain why these three congruences imply that $a^{561}  \equiv a \;(\!\!\!\mod{561})$ for every value of $a$.  Current Solution  Fermat's little theorem states that given a prime $p$, for every $a\in(\mathbb{Z}/p\mathbb{Z})^{\ast}$, \begin{equation*} a^{p-1} \equiv 1 \;(\!\!\!\mod{p}). \end{equation*} Then by Fermat's little theorem, \begin{equation*} a^{561} = a^{2\cdot28}a = \big(a^{28}\big)^2a \equiv a \;(\!\!\!\mod{3}), \end{equation*} \begin{equation*} a^{561} = a^{56 \cdot 10}a = \big(a^{56}\big)^{10}a \equiv a \;(\!\!\!\mod{11}), \end{equation*} \begin{equation*} a^{561} = a^{35\cdot16}a = \big(a^{35}\big)^{16}a \equiv a \;(\!\!\!\mod{17}). \end{equation*}
24822
A composite integer n is a Carmichael number if the only Fermat   witnesses for $n$ are those $a \in \mathbb Z_n^+$ which are not   coprime with $n$. The smallest example of such a number is $561 = 3 ·  11 · 17$   I think I understand the definition, but I don't quite understand why is the smallest Carmichael number is the above mentioned number. Please clarify.
35054
Which of the following primes satisfy the congruence   $$a^{24}\equiv6a+2\pmod{13}$$  1) 41  2) 47  3) 67  4) 83  I am interested in Theorem statement, corollary, or Trick or Logic which solves this problem within one minute. Thank you in Advance
39740
So today in my final for number theory I had to prove that the Fermat numbers ($F_n=2^{2^n}+1$) are coprime.   I know that the standard proof uses the following: $F_n=F_1\cdots F_{n-1}+2$ and then the $\gcd$ divides $2$, and it cannot be two, and hence the numbers are coprime.  However, he asked us to use the hint: "Let $l$ be a prime dividing $F_n$. What can you say about the order of $2$ in $(\mathbb{Z}/l\mathbb{Z})^\times$?"   I have been thinking about it and I cannot figure out how to use his hint.  Any ideas?
34817
So, I decided to work with mod $8$ to help develop some intuition on how to generalize the proof. I noticed that taking $a^2$ to clearly be a perfect square, $a^2$ is always congruent to $0,1,-4,4 \mod 8$, at least for a good finite set of cases. Also, I played around with solutions to $3^m + 3^n + 1 = b$ and seen again for a finite set of cases with $m,n$ varying these were always, $b$ is congruent to $-1,5,-5,3$. Now, I see that well only perfect squares produce a set $\{0,1,-4,4\} \mod 8$ and none of the cases I tried to $m,n$ gave me any of the numbers in this set. And now I'm stuck.
96761
I'm in the process of proving Fermat's little theorem.     For a prime integers $p$ we have $a^p \equiv a \mod{p}$   I proved it for a non-negative $a$, not I need to generalize the case to an arbitrary $a \in \mathbb{Z}$. That is, I need to prove that give a negative integer $a$ we have $a^p \equiv a \mod{p}$ using the fact that it is so for a non-negative $a$.
122809
So I'm trying to find all solutions of $x^2 \equiv$ $a$ mod $p$ and for some reason the formulas that are suggested everywhere online (for example, ) say that, if p is an odd prime and you have a congruence like this:    Then you can find the solutions with this (if there are any):    That's what I was taught as well, but when entering examples into Wolfram Alpha, I've noticed that there are actually more solutions - these formulas just give you one of them! For example:   If I need to find the solutions of: x^2 ≡ 8 (mod 23) and I use the above formulas, I get the solution: x = +- 13, but  (and it does). So why is that? Why do these formulas only give you 1/2 of the answer and why can't I find a way to find the whole answer (excluding the way where you draw the table with x^2 mod p for x from 0 to p and)?  I realize that I'm probably doing something wrong and I'm not very good at this in the first place, but I've spent hours searching for an answer and couldn't really find anything (that I could understand, at least).
116479
Prove that if $p$ and $p+2$ are both prime integers greater than $3$, then $6$ is a factor of $p+1$.  Computing a few primes greater than $3$ modulo $6$ shows the following pattern $5,1,5,\dots$ Thus $$\begin{cases}p\equiv1,5 \pmod{6} \\ p+2 \equiv3,7 \equiv3,1 \pmod{6}\end{cases}$$ Also $p+1 \equiv 2,6 \equiv2,0 \pmod{6}$. I'm not sure how to continue from here... I would like to use modular arithmetic to show this. Is it necessary to remember that every prime can be written as $6n+1$ or $6n+5$ here?
45383
Fermat's little theorem states that if $p$ is a prime number, then for any integer $a$, the number $a^p − a$ is an integer multiple of $p$. In the notation of modular arithmetic, this is expressed as $$a^p \equiv a \mod p.$$  Use Fermat's little theorem to prove that:  Given prime number $p$, show that if there are positive integer $x$ and prime number $a$ such that  $p$ divides   $\frac{x^a – 1}{x – 1}$, then either $а= p$ or $p \equiv 1 \mod a$.  I tried to connect  $\frac{x^a – 1}{x – 1}$ to the theorem, but without any success..  Anything will help.. Thanks in advance
12276
I'm asked to show that $a^{61} \equiv a\pmod{1001}$ for every $a \in \mathbb{N}$. I've tried to tackle this using Fermat's Little Theorem and Euler's Theorem, but I can't even get started. My main problem seems to be the "for every $a \in \mathbb{N}$" part, because if it restricted $\gcd(a, 1001) = 1$ I would be able to factor out 1001 and try to show that it's factors divide $a^{61} - a$. I'm kinda lost here. Any help is appreciated.
48520
Question:  Show that if $\gcd(a,3)=1$ then $a^7 \equiv a\pmod{63} $. Why is this assumption necessary?    Proof:  Since $\gcd(a,3)=1$ $\Leftrightarrow a\equiv 1\pmod 3$ $\Leftrightarrow a^7\equiv 1\pmod3\equiv a\pmod3$  Then using Fermat's Little Theorem:  If $a,p\in\mathbb N$ and $p$ is prime then $a^7\equiv a\pmod7$  $\Rightarrow 3 |a^7-a$ and $7 |a^7-a$  $\Leftrightarrow a^7-a=3k_1$ and $a^7-a=7k_2$  $\Rightarrow (a^7-a)^3=63(k_1)^2k_2$ $\Rightarrow (a^7-a)^3\pmod{63}\equiv 0$  Since $x^m\pmod n\equiv x\pmod n$  $\Rightarrow (a^7-a)^3\pmod{63}\equiv a^7-a\pmod{63}\equiv 0$  $\Leftrightarrow a^7\equiv a\pmod{63}$  The thing I am struggling with is that the question says that the only assumption necessary is that $\gcd(a,3)=1$. Surely there are two assumptions neccessary, since to use Fermat's Little Theorem (in this situation) we need $a\neq 0 \pmod7 \space\space\space(\gcd(a,7)=1)$. I am sure there is something obvious I'm missing -would be great if someone could check over what I have done and point out any mistakes :)
61754
Problem:   If $x^{n-1} \equiv 1 \pmod{n}$, and for all divisors $q$ of $n - 1$, $a^{q} \not\equiv 1 \pmod{n}$, then $n$ is prime. $(n &gt; 1)$   I read the proof in the book and it was very straightforward; however, I wonder is there a way to prove it by just using congruence property?    And another related question about power residue: If we have $a^{n - 1} \equiv 1 \pmod{n}$. Is there any relation between $n - 1$ and $\phi(n)$?  Because I thought of $a^{\phi(n)} \equiv 1 \pmod{n}$, when $(a, n) = 1$. I try to think of away to connect these two ideas, but I still cannot see it. Any idea?    Thanks,
20550
Question: If $p$ is prime and $p$ $\equiv$ $1$ (mod 4), then the congruence $x^2$ $\equiv$ $-1$ (mod $p$) has two incongruent solutions given by $x$ $\equiv$ $\pm$ $\frac{(p-1)}{2}$!(mod $p$).   I noticed that the congruence $x^2$ $\equiv$ $-1$ (mod $p$) fits the form of Wilson's theorem but can't figure out how to modify/change the congruency to fit Wilson's theorem. Sorry if this is a duplicate, I wasn't able to find any other question similar to this one but it could just be my incorrect usage of MathJax.
29040
The question given to me is:     Show that $\large\frac{(3^{77}-1)}{2}$ is odd and composite.   We can show that $\forall n\in\mathbb{N}$:  $$3^{n}\equiv\left\{    \begin{array}{l l}     1 &amp; \quad \text{if $n\equiv0\pmod{2}$ }\\     3 &amp; \quad \text{if $n\equiv1\pmod{2}$}\\   \end{array} \right\} \pmod{4}$$  Therefore, we can show that $3^{77}\equiv3\pmod{4}$. Thus, we can determine that $(3^{77}-1)\equiv2\pmod{4}$. Thus, we can show that $\frac{(3^{77}-1)}{2}$ is odd as:  $$\frac{(3^{77}-1)}{2}\equiv\pm1\pmod{4}$$  However, I am unsure how to show that this number is composite. The book I am reading simply states two of the factors, $\frac{(3^{11}-1)}{2}$ and $\frac{(3^{7}-1)}{2}$, but I do not know how the authors discovered these factors.   I'd appreciate any help pointing me in the right direction, thanks.
4812
Problem: $(\forall a\in\mathbb{Z^+})(m\in\mathbb{Z^+}\to a^m\equiv a^{m-\phi(m)}\pmod{m})$  My work: Start by letting $m=p_1^{a_1}p_2^{a_2}\cdots p_r^{a_r}$. If $(a,p_i)=1$ for some integer $i$, then we have that  $$ a^{\phi(p_i^{a_i})}\equiv 1\pmod{p_i^{a_i}} $$ by Euler's theorem. Since $\phi(p_i^{a_i}) \mid \phi(m)$, we have that $p_i^{a_i}\mid (a^{\phi(m)}-1)$ if $(a,p_i)=1$.   Beyond this, I am stuck at the moment.
58863
Let $n &gt; 1$ be any positive integer and consider $(\mathbb{Z}/n)^\times$. We want to find all elements $x \in (\mathbb{Z}/n)^\times$ such that $x \equiv x^{-1} \mod n$.  After testing a few different $n$, I am certain that the only elements will be $1$ and $n - 1$. This is certainly true when $n$ is prime. Showing it when $n$ is composite is more difficult:  Assume that $x \equiv x^{-1} \mod n$. Then $x^2 \equiv 1 \mod n$ and so $x^2 - 1 \equiv 0 \mod n$, which implies that $(x - 1)(x + 1) \equiv 0 \mod n$. Now if $n$ is prime, we could just conclude that $n | (x - 1)$ or $n | (x + 1)$. But I am unsure what to do in the case that $n$ is composite.
90886
I'm still making my way along in Niven's Intro to Number Theory, and the title problem is giving me a little trouble near the end, and I was hoping someone could help get me through it.  Now $x^8\equiv 16\pmod{2}$ is solvable with $x\equiv 0\pmod{2}$, so I assume $p$ is an odd prime. From a theorem earlier in the text,      If $p$ is a prime and $(a,p)=1$, then the congruence $x^n\equiv a\pmod{p}$ has $(n,p-1)$ solutions or no solution according as $a^{(p-1)/(n,p-1)}\equiv 1\pmod{p}$ or not.   So since $(16,p)=1$, the problem reduces to showing that $16^{(p-1)/(8,p-1)}\equiv 1\pmod{p}$ holds for all $p$. I note that $(8,p-1)$ can only take values $2,4,8$. For $2$, the above equivalence is then $4^{p-1}\equiv 1\pmod{p}$, which is true by Fermat's little Theorem. For $4$, it is then $2^{p-1}\equiv 1\pmod{p}$, which again holds by FlT. However, the case where $(8,p-1)=8$ is throwing me off. At best I see that $16^{(p-1)/8}\equiv 2^{(p-1)/2}\pmod{p}$, but I'm not sure how to show this is congruent to $1$ modulo $p$. Maybe there's a more elegant way to do it without looking at cases. Thanks for any insight.
66062
In Burton's Elementary Number Theory, when introducing absolute pseudoprimes (also called Carmichael numbers), the author states that they are composite numbers $n$ such that $a^{n-1} \equiv 1 \pmod n$ for all integers $a$ with $\gcd(a,n) = 1$.   When showing that 561 is an absolute pseudoprime, he then concludes that $a^{561} \equiv a \pmod{561}$ for all $a$.   I searched a bit on the internet, and it seems that these two are actually equivalent definitions of a Carmichael number. However I have not been able to find a proof; the fact that the implication in the title of the post is stated so plainly in my textbook makes me think it is quite simple to see, but I can't seem to understand the argument.