Modular arithmetic (clock arithmetic) is a system of integer arithmetic based on the congruence relation $a \equiv b \pmod{n}$ which means that $n$ divides $b-a$.

learn more… | top users | synonyms

48
votes
8answers
3k views

The last digit of $2^{2006}$

My 13 year old son was asked this question in a maths challenge. He correctly guessed 4 on the assumption that the answer was likely to be the last digit of $2^6$. However is there a better ...
48
votes
4answers
3k views

Fibonacci number that ends with 2014 zeros?

This problem is giving me the hardest time: Prove or disprove that there is a Fibonacci number that ends with 2014 zeros. I tried mathematical induction (for stronger statement that claims that ...
43
votes
5answers
4k views

Does every prime divide some Fibonacci number?

I am tring to show that $\forall a \in \Bbb P\; \exists n\in\Bbb N : a|F_n$, where $F$ is the fibonacci sequence defined as $\{F_n\}:F_0 = 0, F_1 = 1, F_n = F_{n-1} + F_{n-2}$ $(n=2,3,...)$. How can ...
39
votes
14answers
3k views

'Linux' math program with interactive terminal?

Are there any open source math programs out there that have an interactive terminal and that work on linux? So for example you could enter two matrices and specify an operation such as multiply and ...
28
votes
1answer
762 views

Is $\sqrt1+\sqrt2+\dots+\sqrt n$ ever an integer?

Related: Can a sum of square roots be an integer? Except for the obvious cases $n=0,1$, are there any values of $n$ such that $\sum_{k=1}^n\sqrt k$ is an integer? How does one even approach such ...
25
votes
5answers
4k views

Prove that every year has at least one Friday the 13th

Everyone knows Friday the 13th is regarded as a day of bad luck. Why does every year have at least one of this bad day?
22
votes
2answers
25k views

Finding a primitive root of a prime number

How would you find a primitive root of a prime number such as 761? How do you pick the primitive roots to test? Randomly? Thanks
20
votes
4answers
1k views

Is the number 333,333,333,333,333,333,333,333,334 a perfect square?

I know that if the number is a perfect square then it will be congruent to 0 or 1 (mod 4). Now since the number is even, I know that it is either 0 or 2 (mod 4). How would I go about answering this? ...
16
votes
0answers
474 views

Is every model of modular arithmetic either even or odd?

Modular Arithmetic (MA) has the same axioms as first order Peano Axioms (PA) except $\forall x (Sx \ne 0)$ is replaced with $\exists x(Sx = 0)$. ...
14
votes
5answers
34k views

How to find the inverse modulo m?

For example: $$7x \equiv 1 \pmod{31} $$ In this example, the inverse of $7$ is $9$. How can we find out that $9$? What are the steps that I need to do? Update If I have a general modulo equation: ...
14
votes
2answers
384 views

When is $\binom{n}{k}$ divisible by $n$?

Is there any way of determining if $\binom{n}{k} \equiv 0\pmod{n}$. Note that I am aware of the case when $n =p$ a prime. Other than that there does not seem to be any sort of pattern (I checked up ...
13
votes
6answers
652 views

Show that $\frac{(3^{77}-1)}{2}$ is odd and composite

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 & \quad ...
13
votes
5answers
3k views

If $n$ is composite, then $n$ divides $(n-1)!$.

I have a proof and need some feedback. It seems really obvious that the statement is true but it is always the obvious ones that are a little trickier to prove. So I would appreciate any feedback. ...
13
votes
2answers
354 views

Find a composite number $n$ satisfies $(2+3I)^n≡2-3I\pmod{n}$

As we know if $p$ is an odd prime number then $$(a+bI)^p\equiv a+(-1)^\frac{p-1}2bI\pmod{p},$$ where $I=\sqrt{-1}$. However, is there any composite number $n$ that satisfies ...
13
votes
2answers
451 views

A puzzle with powers and tetration mod n

A friend recently asked me if I could solve these three problems: (a) Prove that the sequence $ 1^1, 2^2, 3^3, \dots \pmod{3}$ in other words $\{n^n \pmod{3} \}$ is periodic, and find the length of ...
12
votes
6answers
1k views

How to find the inverse of 70 (mod 27)

The question pertains to decrypting a Hill Cipher, but I am stuck on the part where I find the inverse of $70 \pmod{ 27}$. Does the problem lie in $70$ being larger than $27$? I've tried Gauss's ...
12
votes
2answers
769 views

nth powers modulo all primes

Let $a \in \mathbb{Z}$, $n \in \mathbb{N}^*$ be integers, and set $P=X^n - a$. Let us consider the three following statements : 1) $P$ has a root in $\mathbb{Z}$ (i.e. $a$ is an nth power) 2) $P$ ...
12
votes
3answers
632 views

Fermat: Last two digits of $7^{355}$

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 ...
12
votes
2answers
348 views

Formula for occurrence of leap years in the Jewish calendar

Over at Judaism.SE, there was a discussion about a formula to determine leap years in the Jewish calendar. Basically, the calendar follows a 19-year cycle, and seven of those years -- 3, 6, 8, 11, 14, ...
12
votes
2answers
258 views

Solve congruence: $45x \equiv 15 \pmod{78}$ (What am I doing wrong?)

Question about solving congruence. I've worked out how to solve them for the most part except for the following problem I'm having: $$45x \equiv 15 \pmod{78}$$ By the euclidean algorithm, I work out ...
11
votes
5answers
326 views

Why are there$ 736$ $2\times 2$ matrices $(M)$ over $\mathbb{Z}_{26}$ for which it holds that $M=M^{-1}$?

I'm currently trying to introduce myself to cryptography. I'm reading about the Hill Cipher currently in the book Applied Abstract Algebra. The Hill Cipher uses an invertible matrix $M$ for ...
11
votes
3answers
3k views

Calculate which day of the week a date falls in using modular arithmetic

In Summer Wars the main character (he is a mathematician) calculates the day of the week of someone's birthday (19/07/1992 is Sunday). I know (very) basic modular arithmetic but I can't figure out how ...
11
votes
1answer
199 views

Solving $n^5+n^4-3=x^2\pmod p$

Prove that for every odd prime number $p$ there is a natural number $n$ such that the equation $n^5+n^4-3=x^2\pmod p$ has no solutions. So we have to understand that for each $p$ we can find $n$ ...
11
votes
2answers
220 views

Is my shorter expression for $ s_m(n)= 1^m+2^m+3^m+\cdots+(n-1)^m \pmod n$ true?

I'm considering the following sums for natural numbers n,m $$ s_m(n)= \sum_{k=1}^{n-1} k^m =1^m+2^m+3^m+\cdots+(n-1)^m $$ modulo n . Looking at odd n first, I found by analysis of the pattern of ...
10
votes
2answers
240 views

Are integers mod n a unique factorization domain?

I am trying to learn abstract algebra from scratch, jolly stuff, but in the process of doing so this puzzles me: Having a ring of integers mod n, where $n=pq$ is composite, as I understand we have ...
10
votes
4answers
1k views

How do I compute $a^b\,\bmod c$ by hand?

How do I efficiently compute $a^b\,\bmod c$: When $b$ is huge, for instance $5^{844325}\,\bmod 21$? When $b$ is less than $c$ but it would still be a lot of work to multiply $a$ by itself $b$ times, ...
10
votes
3answers
1k views

How to find the solutions for the n-th root of unity in modular arithmetic?

$$\begin{align*} x^n\equiv1&\pmod p\quad(1)\\ x^n\equiv-1&\pmod p\quad(2)\end{align*}$$ Where $n\in\mathbb{N}$,$\quad p\in\text{Primes}$ and $x\in \{0,1,2\dots,p-1\}$. How we can find the ...
10
votes
1answer
428 views

Why are the only numbers $m$ for which $n^{m+1}\equiv n \pmod{m}$ is true also unique for $\displaystyle\sum_{n=1}^{m}{n^m}\equiv 1 \bmod m$?

It can be seen here that the only numbers for which $n^{m+1}\equiv n \pmod{m}$ is true are 1, 2, 6, 42, and 1806. Through experimentation, it has been found that ...
9
votes
7answers
3k views

Pattern to last three digits of power of $3$?

I'm wondering if there is a pattern to the last three digits of a a power of $3$? I need to find out the last three digits of $3^{27}$, without a calculator. I've tried to find a pattern but can not ...
9
votes
4answers
1k views

solve $100x - 23y = -19$

I need help with this equation $$100x - 23y = -19.$$ When I plug this into Wolfram|Alpha, one of the integer solutions is $x = 23n + 12$ where $n$ is a subset of all the integers, but I can't seem to ...
9
votes
4answers
1k views

Why is n mod 0 undefined?

I tried to find out what $n$ mod $0$ is, for some $n\in \mathbb{Z}$. Apparently it is an undefined operation - why?
9
votes
2answers
1k views

Very simple question, but what is the proof that x.y mod m == ((x mod m).y) mod m?

I apologise for this question, as it is no doubt very simple, but I've never been very confident with proofs. Our lecturer today (in a course related to maths but not mathematical itself) was playing ...
9
votes
1answer
189 views

Elementary Number Theory; prove existence

Prove that there exists a positive integer $n$ such that $$2^{2012}\;|\;n^n+2011.$$ I was wondering if you could prove this somehow with induction (assume that $n$ exists for $2^k|n^n+2011$ ...
8
votes
6answers
401 views

Fermat's Little Theorem: exponents powers of p

I was working with congruence classes and encountered Fermat's little theorem: $$a^{p } \equiv a \mod p$$ But I noticed that a$^{p^{k}} \equiv a \mod p$. I used induction on $k$ but I'm still not ...
8
votes
2answers
937 views

The modular curve X(N)

I have a question about the modular curve X(N), which classifies elliptic curves with full level N structure. (A level N structure of an elliptic curve E is an isomorphism from $Z/NZ \times Z/NZ$ to ...
8
votes
4answers
1k views

Remainder when $20^{15} + 16^{18}$ is divided by 17

What is the reminder, when $20^{15} + 16^{18}$ is divided by 17. I'm asking the similar question because I have little confusions in MOD. If you use mod then please elaborate that for beginner. ...
8
votes
4answers
276 views

A solution to $y^5 \equiv 2\pmod{251} $

I need to show that the following equation has a solution. (I am not asked for the answer, which I know by Mathematica to be $y=43$. ) $y^5 \equiv 2 \pmod{251}. $ I know that the order of 2 is 50, ...
8
votes
1answer
457 views

Prove that $n$ must be prime.

Here is the complete question: Suppose that $n=2^{m}h+1$, where m is an integer and $h$ is an odd positive integer less than $2^{m}$. Suppose that there is an integer $a$ such that ...
8
votes
1answer
1k views

Is there a way to find the first digits of a number?

Is there a way to find the first digits of a number? For example, the largest known prime is $2^{43,112,609}-1$, and I did sometime before a induction to find the first digit of a prime like that. ...
8
votes
1answer
154 views

An analogue of Hensel's lifting for Fibonacci numbers

In this question Oleg567 conjectured the following interesting fact about Fibonacci numbers: $$ k\mid F_n\quad\Longrightarrow\quad k^d\mid F_{k^{d-1}n} $$ that can be regarder as an analogue of the ...
8
votes
1answer
97 views

Prove that $\forall p \in \Bbb P;p \ne 5,$ $F_{p^n - \left(\frac{5}{p}\right)p^{n-1}} \equiv 0 \mod p^n$

Prove that $\forall p \in \Bbb P,n \in \Bbb Z^+;p \ne 5,$ $F_{p^n - \left(\frac{5}{p}\right)p^{n-1}} \equiv 0 \mod p^n$ and $F_{5^n} \equiv 0 \mod 5^n$, where $\left(\dfrac{5}p\right)$ is the Legendre ...
8
votes
1answer
93 views

Finding the generators of a subgroup of $\mathrm{SL}_2(\mathbb Z)$

I am trying to solve the following problem: Let $T_{ij}(c)\in\mathrm{SL}_2(\mathbb Z)\ (i\neq j)$ be the elementary matrix which represents the elementary row operation of adding the $j$-th row ...
7
votes
4answers
1k views

Calculating 7^7^7^7^7^7^7 mod 100

What is $$\large 7^{7^{7^{7^{7^{7^7}}}}} \pmod{100}$$ I'm not much of a number theorist and I saw this mentioned on the internet somewhere. Should be doable by hand.
7
votes
4answers
4k views

Modular exponentiation using Euler’s theorem

How can I calculate $27^{41}\ \mathrm{mod}\ 77$ as simple as possible? I already know that $27^{60}\ \mathrm{mod}\ 77 = 1$ because of Euler’s theorem: $$ a^{\phi(n)}\ \mathrm{mod}\ n = 1 $$ and $$ ...
7
votes
4answers
344 views

A “fast” way to manually compute $3^{41}+7^{41} \pmod{13}$

The problem: Find the remainder of $3^{41}+7^{41}$ when divided by $13$. My approach is by utilizing the cyclicity of remainders for examples $3^1,3^2,3^3,3^4,3^5 \text{ and }3^6$ when divided ...
7
votes
3answers
364 views

Why do the gaussian integers have only 2 congruence classes mod 1+i?

If we consider $Z[i]$ modulo $1+i$, why are there only two congruence classes?
7
votes
2answers
244 views

$3x^2 ≡ 9 \pmod{13}$

What is $3x^2 ≡ 9 \pmod{13}$? By simplifying the expression as $x^2 ≡ 3 \pmod{13}$ and applying brute force I can show that the answers are 4 and 9, but how to approach this in a more efficient way? ...
7
votes
3answers
138 views

How to prove that $53^{103}+ 103^{53}$ is divisible by 39?

This is a problem in my number theory textbook. It is based on modular arithmetic but im not getting how to start off to prove this. Please give me some hints on how to solve it.
7
votes
3answers
1k views

Showing $x^8\equiv 16 \pmod{p}$ is solvable for all primes $p$

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 ...
7
votes
3answers
490 views

Number of integers not divisible by $p$ and $q$

Here's a part of question from Siklos' "Advanced Problems in Core Mathematics": How many integers greater than or equal to zero and less than 1000 are not divisible by 2 or 5? What is the average ...