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

128
votes
1answer
7k views

A variation of Fermat's little theorem

Fermat's little theorem states that for $n$ prime, $$ a^n \equiv a \pmod{n}. $$ The values of $n$ for which this holds are the primes and the Carmichael numbers. If we modify the congruence ...
57
votes
4answers
4k 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 ...
49
votes
9answers
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 ...
46
votes
5answers
5k 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 ...
40
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 ...
37
votes
13answers
5k views

How to prove that the Fibonacci sequence is periodic mod 5 without using induction?

The sequence $(F_{n})$ of Fibonacci numbers is defined by the recurrence relation $$F_{n}=F_{n-1}+F_{n-2}$$ for all $n \geq 2$ with $F_{0} := 0$ and $F_{1} :=1$. Without mathematical induction, ...
29
votes
3answers
34k 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
26
votes
5answers
5k 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?
25
votes
1answer
289 views

Fibonacci $\equiv -1 \mod p^2$

Is there a prime $p > 3$ such that the Fibonacci number $F_{np} \equiv -1 \mod p^2$ for some natural number $n$? I know none of the first $1000$ primes $> 3$ qualify. EDIT: In response to ...
22
votes
5answers
44k views

How to find the inverse modulo m?

For example: $$7x \equiv 1 \pmod{31} $$ In this example, the modular inverse of $7$ with respect to $31$ is $9$. How can we find out that $9$? What are the steps that I need to do? Update If I have ...
21
votes
5answers
2k views

Number of consecutive zeros at the end of $11^{100} - 1$.

How many consecutive zeros are there at the end of $11^{100} - 1$? Attempt Trial and error on Wolfram Alpha shows using modulus shows that there are 4 zeros (edit: 3 zeros, not 4). Otherwise, I have ...
20
votes
4answers
2k 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 ...
18
votes
3answers
4k views

Why does (1/3) mod 3016 = 2011?

So I am taking a class where we are working on a cryptography section. Basically, the course says that: $$\frac 1 3 \mod(3016) = 2011$$ or when run through Python - modified with SciPi: $$\frac 1 3 ...
17
votes
6answers
2k views

Linear diophantine equation $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 ...
17
votes
1answer
518 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)$. ...
16
votes
2answers
424 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 ...
16
votes
2answers
2k views

what is the remainder when $1!+2!+3!+4!+\cdots+45!$ is divided by 47?

Can any one please tell the approach or solve the question what is the remainder when $1!+2!+3!+4!+\cdots+45!$ is divided by $47$? I can solve remainder of $45!$ divided by $47$ using Wilson's ...
15
votes
5answers
3k views

Is it true that the Fibonacci sequence has the remainders when divided by 3 repeating?

About this Fibonacci sequence, is it true that the remainders when divided by three repeat along with the sequence like this: Fibonacci sequence: $1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, ...
15
votes
1answer
110 views

pattern in decimal representation of powers of 5

The first few powers of $5$ are given by: \begin{array}{r} 5 \\ 25 \\ 125 \\ 625 \\ 3125 \\ 15625\\ 78125\\ 390625\\ ...
14
votes
7answers
1k views

Why do remainders show cyclic pattern?

Let us find the remainders of $\dfrac{6^n}{7}$, Remainder of $6^0/7 = 1$ Remainder of $6/7 = 6$ Remainder of $36/7 = 1$ Remainder of $216/7 = 6$ Remainder of $1296/7 = 1$ This pattern of ...
14
votes
4answers
2k 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, ...
13
votes
6answers
667 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
4k 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
3answers
923 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 ...
13
votes
2answers
279 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 ...
13
votes
2answers
359 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
548 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
7answers
1k views

How do I prove that there infinitely many rows of Pascal's triangle with only odd numbers?

This is exercise number $59$ from Chapter $2$ of Hugh Gordon's Discrete Probability. Show that there are infinitely many rows of Pascal's Triangle that consist entirely of odd numbers. ...
12
votes
4answers
2k views

In mod3, is 3 greater than, or less than 1?

In modular arithmetic (say mod3), is the largest number (3) greater than or less than the smallest number? Because, intuitively, it would be greater, but 3+1=1 in mod3 which would suggest that it is ...
12
votes
4answers
3k 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?
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
873 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
419 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
133 views

Remainders of Fibonacci numbers

Let $a>b$ be positive integers. Is there a Fibonacci number that is $b$ modulo $a$? We know that the Fibonacci numbers are periodic modulo $a$. Indeed, consider pairs $(F_i,F_{i+1})$ modulo $a$. ...
12
votes
1answer
177 views

Representing predicate logic as arithmetic

Summary Since the below is quite long, I thought I'd add this summary. Given the following: A statement in proposition logic can be converted to an arithmetic expression over the integers modulo ...
11
votes
2answers
1k 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 ...
11
votes
5answers
412 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
4k 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

A proof involving the Euler phi function

Problem: Let $\varphi$ be the Euler phi function, where for any $n \in \mathbb{Z^+}$, $\varphi(n)$ is the number of positive integers less than $n$ that are relatively prime with $n$. ...
11
votes
2answers
116 views

Prove $x^5-2$ is irreducible over $\mathbb{Z}_{31}$

I am currently studying for my Algebra Qualifying Exam. I came across the following problem and am stuck on where to even begin: Prove that $x^5-2$ is irreducible over $\mathbb{Z}_{31}$. I have ...
11
votes
1answer
215 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
237 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 ...
11
votes
3answers
283 views

Finding $n$ satisfying $\{1^n-0^n,2^n-1^n,\cdots,p^n-(p-1)^n\}\equiv \{0,1,\cdots,p-1\}\pmod p$

Background : About a month ago, a friend of mine taught me his findings about a few polynomials which cover all the residue classes in mod $p$ where $p$ is a prime. Then, I began to consider the same ...
10
votes
3answers
95 views

Show that for every prime $p$, there is an integer $n$ such that $2^{n}+3^{n}+6^{n}-1$ is divisible by $p$.

So the problem states: Show that for every prime $p$, there is an integer $n$ such that $2^{n}+3^{n}+6^{n}-1$ is divisible by $p$. I was thinking about trying to prove this using the corollary to ...
10
votes
2answers
304 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
3answers
2k 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
431 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
4k 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
5answers
14k views

How do you calculate the modulo of a high-raised number?

I need some help with this problem: $$439^{233} \mod 713$$ I can't calculate $439^{223}$ since it's a very big number, there must be a way to do this. Thanks.
9
votes
2answers
2k views

Order of an Element Modulo $n$ Divides $\phi(n)$

How can I show that the order of an element modulo $n$ divides $\phi(n)$? I know that if $a$ and $n$ are relatively prime, then the least positive integer $x$ such that $a^x\equiv1\pmod n$ is its ...