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

40
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
4answers
2k 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 ...
38
votes
14answers
2k 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
693 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?
18
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? ...
17
votes
2answers
20k 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
16
votes
0answers
356 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
2answers
353 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
633 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
2answers
352 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
386 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
5answers
2k 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. ...
12
votes
6answers
766 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
692 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
2answers
319 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
240 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
28k 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: ...
11
votes
3answers
353 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 ...
11
votes
5answers
310 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
2answers
203 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
214 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
955 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
425 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
2k 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
2answers
892 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
183 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
4answers
572 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?
8
votes
2answers
808 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
735 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
268 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
427 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
91 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
88 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
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
6answers
377 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 ...
7
votes
3answers
333 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
4answers
338 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
2answers
243 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
389 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 ...
7
votes
1answer
60 views

Halving One in Odd Size Rings

Consider the rings $\mathbb{Z} /n \mathbb{Z}$ where $n$ is odd. Every number is even in such rings. Assume we start with $1$ and keep "halving" until we get back to $1$. What can be said about the ...
7
votes
2answers
166 views

How many solutions does $x^2 \equiv {-1} \pmod {365}$ have?

How many solutions does $x^2 \equiv {-1} \pmod {365}$ have? My thought: $365 = 5 \times 73$ where $5$ and $73$ are prime numbers. So we can obtain $x^2 \equiv {-1} \pmod 5$ and $x^2 \equiv ...
7
votes
1answer
102 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 ...
7
votes
1answer
74 views

$ 7\mid x \text{ and } 7\mid y \Longleftrightarrow 7\mid x^2+y^2 $

Show that $$ 7\mid x \text{ and } 7\mid y \Longleftrightarrow 7\mid x^2+y^2 $$ Indeed, First let's show $7\mid x \text{ and } 7\mid y \Longrightarrow 7\mid x^2+y^2 $ we've $7\mid x ...
7
votes
1answer
122 views

A proof in number theory dealing with modular congruences.

So we are asked to show that $$(p-1)(p-2)\cdots(p-r)\equiv (-1)^{r}r! \pmod{p}$$ for $r=1,2,...,p-1$. I worked on it and I want to know if my proof suffices to show what is being asked. I would also ...
7
votes
1answer
309 views

Is there formal name and proof for this formula/theorem (for now I'm calling it Orbital Collinearity Theorem)?

Suppose you are given a question that goes like this: Consider three planets that revolve around a star on separate circular orbits sharing the same orbital plane. The first planet, A, takes ...
6
votes
5answers
347 views

Basic question about mod

I'm having a tough time understanding why $(a^x \bmod p)^y \bmod p$ is equal to $a^{xy}\bmod p$. Does this have a mathematical proof? Please advise.