I'm having some trouble proving the following:  Let $d$ be the smallest positive integer such that $a^d \equiv 1 \pmod m$, for $a \in \mathbb Z$ and $m \in \mathbb N$ and with $\gcd(a,m) = 1$. Prove that, if $a^n \equiv 1 \pmod m$ then $d\mid n$.  The first thing that came to my mind was Euler's theorem but I couldn't conclude anything because I'm not very skilled when it comes to using Euler's totient function. Can someone give me any tips or show me how to solve this?
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.
27107
Let $a\ge 2$ be an integer. Show that for positive integers $m,n$, we have $a^n - 1$ divides $a^m - 1$ if and only if $n$ divides $m$.   I am having trouble showing this. I've seen a similar problem on here but it only shows one direction for the proof. I would like to see both directions.  This is what I have so far: Let $m = nq + r$, then $a^m - 1 = a^{nq + r}- 1 = a^{nq}a^r - 1 = a^{nq}a^r - a^r + a^r - 1 = a^r(a^{nq} - 1) + a^r - 1$. Since $0\le r\lt n$, $r = 0$ then $a^m - 1$ = $a^{nq} - 1$ so $a^m$ = $a^{nq}$ . Thus $m = nq$ hence $n\mid m$.
27206
a, b are integers. p is prime. I want to prove: $(a+b)^{p} \equiv a^p + b^p \pmod p$  I know about Fermat's little theorem, but I still can't get it I know this is valid: $(a+b)^{p} \equiv a+b \pmod p$ but from there I don't know what to do.  Also I thought about $(a+b)^{p} = \sum_{k=0}^{p}\binom{p}{k}a^{k}b^{p-k}=\binom{p}{0}b^{p}+\sum_{k=1}^{p-1} \binom{p}{k} a^{k}b^{p-k}+\binom{p}{p}a^{p}=b^{p}+\sum_{k=1}^{p-1}\binom{p}{k}a^{k}b^{p-k}+a^{p}$ Any ideas?  Thanks!
70953
I believe that this may require the use of Fermat's Little Theorem. I rewrote it as $(a+1)^p - a^p \equiv 1 \pmod{p}$ because the right-hand side looks similar to Fermat's Little Theorem, but I was unable to figure out how I can get the left-hand side to become $a^{(p-1)}$.
80346
I'm having some trouble proving the following proposition:  Let $m \in \mathbb N$ and $a,b,k \in \mathbb Z$, then: $$ka \equiv kb \pmod{m} \iff a \equiv b \pmod{\frac{m}{\gcd(k,m)}}$$  I began by trying to prove that $a \equiv b \pmod{\frac{m}{\gcd(k,m)}} \implies ka \equiv kb \pmod{m}$ but I got stuck with: $$a\gcd(k,m) \equiv b \gcd(k,m) \pmod{n}$$ Then I also tried to prove that $ka \equiv kb \pmod{m} \implies a \equiv b \pmod{\frac{m}{\gcd(k,m)}}$ But I also was not able to conclude anything. This is my first time learning modular arithmetic and I'm still confused with the concepts and have no intuition with this at all, this is perhaps why I'm having some trouble solving these types of questions. How can I prove this?
77523
I've been asked to show that:  $n(n+1)(2n+1) \equiv 0 \pmod 6$  I found in a previous question that:  $n(n+1)$ was divisible by $2$ and resulted in an even number e.g  $n(n+1) \equiv 0 \pmod 2$  so I figured I needed to find:  $(2n+1) \equiv 0 \pmod 3$ in order to complete  $n(n+1)(2n+1) \equiv 0 \pmod 6$  but I am unsure on how to find $(2n+1) \equiv 0 \pmod 3$  Is this the right way to find the mod 6 and if so could you tell me how I could find  $(2n+1) \equiv 0 \pmod 3?$
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
68761
I found the following question and can't make much headway with it.  Show that there exist infinitely many positive integers $n$ such that $2^n \equiv n \mod p$ where $p$ is a odd prime...  I started by writing the number as $n=(p-1)k+c$ which implies $$2^c \equiv c-k \mod p$$ where I used Fermat's Little theorem. Now if $k$ is of the form $pm$ for some integer $m$ we get $n=(p-1)(p)m+c$   $$2^c \equiv c \mod p$$ and we have reduced $n$ to some smaller integer $c$ but I can't figure out how to find the smallest number $c$ which would then generate infinitely many $n$.  Any help in finding a possible approach to this would be highly appreciated.
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,
109349
If $m,n&gt;1$ are integers such that $g.c.d.(m,n)=1$ then is it true that there are at-least four elements in $\mathbb Z_{mn}$ such that $x^2=x$ ( i.e. idempotent ) ?
21541
For any nonzero integers $ a $ and $ b $, there exist integers $ s $ and $ t $ such that $ \gcd(a,b) = as + bt $. Moreover, $ \gcd(a,b) $ is the smallest positive integer of the form $ as + bt $.  I know of one proof of this question, in which we consider $$ S = \{ am + bn ~|~ \text{$ m,n \in \mathbb{Z} $ and $ am + bn &gt; 0 $} \}, $$ but I didn’t manage to get the proof. Can someone please explain this theorem?
49659
Can anyone help me out here? Can't seem to find the right rules of divisibility to show this:  If $a \mid m$ and $(a + 1) \mid m$, then $a(a + 1) \mid m$.
6856
Here is a problem which i have not been able to do for quite sometime.   For $n \geq 2$, show that $n \nmid 2^{n}-1$.   I have thought of proving this in two ways: One by using induction which didn't actually work. Next by Fermat's little theorem we have $2^{p-1} \equiv 1 \ (\text{mod} \ p)$, which actually says that for $p \mid 2^{p}-2$. But i couldn't proceed more than this. Any ideas by which i can actually solve the problem?
53347
Prove that if $m\not =n,a$ are positive integers then $(a^{2^n}+1,a^{2^m}+1)$ is $1$ if $a$ is even and $2$ if $a$ is odd.    I solve the problem in the following way: I assume that $m&gt;n$ then  $$a^{2^m}+1=a^{2^m}-1+2$$ With this expression if I take a divisor prime $p$ of $a^{2^n}+1$ then if $p|a^{2^m}+1$ this prime must divide 2 and the result follows.   But, how can I prove this statement without use of primes? This exercise appears before the concept of prime is introduced then I prefer do not use it.    Any idea?   Thanks!
8673
From A Classical Introduction to Modern Number Theory by Ireland and Rosen, page 33:     Corollary 1 (Euler's Theorem). If $(a,m) = 1$, then $a^{\phi(m)} \equiv 1\,(m)$.      Proof. The units in $\mathbb{Z}/m\mathbb{Z}$ form a group of order $\phi(m)$. If $(a,m) = 1$, $\bar{a}$ is a unit. Thus $\bar{a}^{\phi(m)} = \bar{1}$ or $a^{\phi(m)} \equiv 1\,(m)$.   If I'm interpreting this correctly, this proof implicitly uses the fact(?) that if $G$ is a group and $x\in G$, then $x^{|G|}=1$, where $1$ is the identity element of $G$.  If this is indeed true, can someone explain why? (I have had no prior exposure to group theory.)
117827
Establish that if $a$ is an odd integer, then for any $n\ge1$ $$a^{2^n}\equiv1\pmod{2^{n+2}}.$$   [Hint: Proceed by induction on $n.$]   This is a problem from Elementary Number Theory by David M. Burton.  For $\underline{n=1},$ this statement is essentially saying that $$a^2\equiv1\pmod{2^3=8},$$ which is true because $a$ is odd. Suppose that this statement is true for $\underline{n=k}$. Then,$$a^{2^k}\equiv 1\pmod{2^{k+2}}.$$ Squaring this congruence, I arrived at $$a^{2^{k+1}}\equiv1\pmod{2^{k+2}},$$ but how do I change the modulus, i.e., $\pmod{2^{k+2}}\to\pmod{2^{k+3}}?$
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.