By Fermat's theorem (or more generally by Euler's totient function theorem), for $p$ prime, any nonzero element $a$ of $Z/pZ$ satisfies:  $$a^{p-1}\equiv1 \mod p$$  Hence, in this case, we have  $$9^{74}=(9^{12})^69^2$$  Applying the theorem:  $$9^{12}\equiv1 \mod 13$$  So   $$9^{74}\equiv9^2 \mod 13$$  And now, if I'm doing the math correctly,  $$81=(13)(6)+3$$  So  $$81\equiv3 \mod 13$$  Is this correct?
3352
I've read about Fermat's little theorem and generally how congruence works. But I can't figure out how to work out these two:   $13^{100} \bmod 7$ $7^{100} \bmod 13$   I've also heard of this formula:  $$a \equiv b\pmod n \Rightarrow a^k \equiv b^k \pmod n $$  But I don't see how exactly to use that here, because from $13^1 \bmod 7$ I get 6, and $13^2 \bmod 7$ is 1. I'm unclear as to which one to raise to the kth power here (I'm assuming k = 100?)  Any hints or pointers in the right direction would be great.
12941
The proof is a follows:  Let $p$ be a prime number and $x$ in Z. If $x^2\equiv1\pmod p$ then $x\equiv\pm1\pmod p$.  Proof: By assumption, $p | x^2 - 1 = (x + 1)(x - 1)$. Thus $p | x + 1$ or $p | x - 1$. This completes the proof.    However if $p | x + 1$ then $x$ is congruent to $-1 \mod p$. However why is $p$ congruent to $1 \mod p$ ??   I'm struggling seeing this, and been sitting for some hours now trying to figure it out - please help.
86119
I know how to find for which $n$ $\phi(n)=n/2$ or $\phi(n)=n/3$, my method for finding those was simply to find primes $p$ that satisfy $\Pi_p$$_|$$_n$$1-1/p$ $  = 1/2$ or $1/3$.  However, I don't know how to find $\Pi_p$$_|$$_n$$1-1/p = n/6$. Intuitively it seems that if I combine results for both $\phi(n) = n/2$ and $\phi(n) = n/3$ I'll get $\phi(n) = n/6$ but it does not work, cause I get number of the form $2^a3^b$ which gives $\phi(n) = n/3$ again.  Is there a way to find $n$ for which $\phi(n)=n/6$? Or do such numbers exist at all?
97026
Solve $[2^{(2^{403})}] = [a]$ in $\mathbb Z_{23}$ where $0 \le a &lt; 23$.  I've tried to combine corollaries of Fermat's little theorem and various other methods to solve this, but have always been stuck.
24727
I need to prove that:  If $p$ is prime greater than or equal to five, then $pB_{p-1}$ belongs to the p-integers and more over:  $$pB_{p-1} \equiv -1 \pmod p$$ Hint:Put $N=p$ in the Faulhaber´s formula: $S_{j}(N-1)=  \displaystyle\sum_{k=o}^j \frac{1}{(j-k+1)}{j \choose k}N^{j-k+1}B_{k}$ and reduce everything mod p and use the Fermat´s little theorem.  But I do not know how to reduce this:  $S_{j}(p-1)=  \displaystyle\sum_{k=o}^j \frac{1}{(j-k+1)}{j \choose k}p^{j-k+1}B_{k}$ to mod p,and I have problems trying to prove that $pB_{p-1}$ belongs to the p-integers, Can you help to prove the theorem please, Thank you.
65102
I've just started a cryptography course, so i am not experienced at all how to calculate such big numbers. Clearly, i can't use a calculator, because the number is too big, so i have to calculate it by hand.   Since $101$ is a prime number, i think i should use here Fermat's little theorem. Found some example and tried to solve it this way, but i am totally not sure, if it is correct and if my approach must be this one.   Calculate $5^{3^{1000}}\bmod 101$.  First of all i think i should calculate $3^{1000}\bmod 101$. From Fermat's little theorem i get to $3^{100}\equiv 1\bmod 101$.   Thus $1000=x100+0$ and $x=10$.   $3^{1000}\equiv 3^{999^{10}}  = 1 ^{10} \equiv 102\bmod 101 $  Later i have to calculate $5^{102}\bmod 101$.  Again by Fermat $5^{100}\equiv 1\bmod 101$.  $$102=100\cdot 1 +2$$  Here i am not sure how to move on... I think that my solution is wrong, but i'd love to see your suggeststions and remarks how to solve the problem.  Thank you very much in advance!
41140
While I was surfing the web, searching things about math, I read something about a particular theorem of Fermat. It said: let $a$ and $b$ be rational. Then $a^4-b^4$ cannot equal the square of a rational number, so $a^4-b^4\neq c^2$ with $c$ rational. My question is: did I understand the theorem? if not, what is the actual theorem? if yes, how can I proof this or is that too difficult?
17911
I am doing this problem mentioned above and I know the answer because I know Euler's Theorem that $$a^{\varphi{(m)}}\equiv{1}\pmod{m}.$$  I used 100 as my modulus and got that the last two digits of $7^{355}$ are $43$.  My question is this.  What prime should I pick to solve this problem using Fermat's theorem $$a^{p-1}\equiv{1}\pmod{p}$$  As a precursor problem, the author (Dudley; Elementary Number Theory) asked to find the last digit of the number above; so using a modulus $5$, $7^4\equiv{1}\pmod{5}$ by Fermat.  Since the answer is $7^{355}\equiv{3}\pmod{5}$, the last digit is either $3$ or $8$.  Since $7$ is odd, the answer will clearly be odd, so $3$ is it.  The book is working linearly, building from the previous chapters and Euler's Theorem isn't mentioned for another two chapters (I remembered Euler from a problem solving class in college).    So again, what prime would be best?  How should I procede?    EDIT: I've seen a bunch of problems on the site and none that I looked at did it using Fermat.  If there is one, that could be posted and I would be happy.  EDIT 2:  it seems that the problem of finding of finding the last two digits using is rather difficult because of the implication that we need something mod 100.  Is there a way around this , like adding a step or complexifying, in order to finish the problem with Fermat?
101406
How can I prove Euler's Theorem:   $$x^{\phi(m)+1} \equiv x \pmod m$$   is still true when $x$ is not relatively prime to $m$?  Edit: when m=pq where p and q are distinct primes
101065
let $p$ be a prime and let $a$ be an integer not divisible by $p$, that is $(a,p)=1$. Then $\{a,2a,3a,...,pa\}$ is a complete residue system modulo $p$.  Since $p\nmid a$, $p\nmid\{a,2a,3a,...,(p-1)a\}$ Since $p|p$, $p|\{pa\}$ which is exactly one element in the set and is therefore a complete residue system.   Wondering if this is an acceptable proof to this theorem.
26975
Using Fermat's Theorem prove if $p$ is prime, prove $1^p + 2^p + 3^p +...+(p-1)^p \equiv 0 \bmod{p}$  The two definitions of Fermat's Little Theorem is $a^p \equiv a \bmod{p}$ and $a^{p-1} \equiv 1 \bmod{p}$ but I don't know how to use this solve the problem
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,
32288
Consider the following  (I read similar thing in a couple of sources but this one illustrates the issue I'm having):     By Fermat's Theorem if $n$ is prime, then for any $a$ we have $a^{n-1} = 1 \pmod{n}$. This suggests the Fermat test for a prime: pick a random $a \in \{1,...,n-1\}$ and see if $a^{n-1} = 1 \pmod{n}$. If not, then $n$ must be composite.      However we may still get equality even when $n$ is not prime. For example, take $n = 561 = 3\times 11\times 17$. By the Chinese Remainder Theorem ... (Some explanation)      Thus no matter what $a$ we pick, $561$ always passes the Fermat test despite being composite so long as $a$ is coprime to $n$. Such numbers are called Carmichael numbers, and it turns out there are infinitely many of them.   So according to the author, no matter what $a \in \{1,...,n-1\}$ we choose, 561 will pass the test. But this is not true e.g:  $$ \begin{align} 3^{560} &amp;\not\equiv 1 \pmod{561} \\ 6^{560} &amp;\not\equiv 1 \pmod{561} \\ 9^{560} &amp;\not\equiv 1 \pmod{561} \\ &amp;... \end{align} $$  and there are many $a \in \{1,...,n-1\}$ such that $a^{560} \not\equiv 1 \pmod{561}$.  Why would we exclude $a$ such that $\gcd(a, n) = 1$ when the test works well without such condition? If we know that $\gcd(a, n) \not= 1$, we already know that $n$ is not prime, thus the test is pointless.  The best source I read so far, sadly forget it, states that if $n$ is composite, then 50% of $a \in \{1,...,n-1\}$ will not satisfy $a^{n-1} \equiv 1 \pmod{n}$. Unless it's Carmichael numbers, i.e. there are less than 50%. Which seams true in my experiences (and this is properly the reason why the probability of not being prime gets lower by $1/2$ on each iteration).
5410
Prove: if $n\mid 7^n+6^n$ and $n&gt;1$, then $13\mid n$  Let $p$ be the least prime number such that $p\mid n$.   And I want to show that $p=13$  Let $d$ be the least number such that: $14^d\equiv 0 \pmod {p}$  And by Fermat's little theorem I have: $14^{p-1}\equiv 0 \pmod{p}$  Here I'm stuck
81416
I know that there is a similar post, but I 'm trying a different proof. I will write $P$  for the set of all positive prime numbers. Question: If $\phi$ is Euler's Phi Function, we want to find all $n \in \mathbb{Z^+}$ such that $\phi(n)=4$. Answer: Let $n=p_1^{n_1}\dotsb p_k^{n_k}\in \mathbb{Z}^+$ be the factorisation of $n$ in to primes. Then $$\phi(n)=p_1^{n_1-1} \dotsb p_k^{n_k-1}(p_1-1) \dotsb (p_k-1)=4.$$ So, for any $i \in \{1,2,\cdots,k\}$ we have $p_i-1|4$. Hence, $$p_i-1\in\{1,2,4\} \iff p_i\in \{2,3,5\} \subset P.$$ Now, we can see the primes that $n$ contains: $n=2^{n_1}3^{n_2}5^{n_3}$, where  $n_1,n_2,n_3 \in \mathbb{Z}^+$. So, \begin{align*} \phi(2^{n_1}3^{n_2}5^{n_3})=4 \iff \phi(2^{n_1})\phi(3^{n_2})\phi(5^{n_3})=4  \tag{*} \end{align*} The possible cases for $n_i$ are:  $n_1=1,2,3\implies \phi(2)=1,\phi(2^2)=2, \phi(2^3)=4$ respectively $n_2=1 \implies \phi(3)=2$ $n_3=1 \implies \phi(5)=4$  All the posible combinations for the relation (*) are $\phi(5)$, $\phi(5)\phi(2)$, $\phi(3)\phi(2^2)$, $\phi(2^3)$. So, $$n \in \{5,10,12,8\}.$$ Is this completely right? Thank you.
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.
109233
If a prime $p$ divides a Fermat Number then $p=k\cdot 2^{n+2}+1$?   Does anyone know a simple/elementary proof?