Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [modular-arithmetic]

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 $a-b$.

159
votes
1answer
8k views

A variation of Fermat's little theorem in the form $a^{n-d}\equiv a$ (mod $p$).

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 ...
97
votes
6answers
7k 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 ...
94
votes
11answers
29k views

Is zero odd or even?

Some books say even numbers start from two but if you consider the number line concept, I think zero ($0$) should be even because it is in between $-1$ and $+1$ (i.e in between two odd numbers). What ...
85
votes
9answers
11k 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, ...
83
votes
4answers
3k views

How to solve these two simultaneous “divisibilities” : $n+1\mid m^2+1$ and $m+1\mid n^2+1$

Is it possible to find all integers $m>0$ and $n>0$ such that $n+1\mid m^2+1$ and $m+1\,|\,n^2+1$ ? I succeed to prove there is an infinite number of solutions, but I cannot progress anymore. ...
81
votes
3answers
117k 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
72
votes
3answers
3k views

Mathematicians shocked(?) to find pattern in prime numbers

There is an interesting recent article "Mathematicians shocked to find pattern in "random" prime numbers" in New Scientist. (Don't you love math titles in the popular press? Compare to the source ...
66
votes
6answers
10k views

Why is $9$ special in testing divisiblity by $9$ by summing decimal digits? (casting out nines)

I don't know if this is a well know fact but I have observed that every number no matter how large that is equally divided by $9$, will equal $9$ if you add all the numbers it is made from until there ...
61
votes
5answers
7k 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 ...
59
votes
7answers
6k 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 ...
56
votes
7answers
136k 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 ...
52
votes
2answers
2k views

Fractals using just modulo operation

Let us calculate the remainder after division of $27$ by $10$. $27 \equiv 7 \pmod{10}$ We have $7$. So let's calculate the remainder after divison of $27$ by $7$. $ 27 \equiv 6 \pmod{7}$ Ok, so ...
50
votes
6answers
6k views

Why does adding a suitable multiple of $9$ always lead to the reverse of the number?

For example: $12$ reversed is $21$ and $12$ + $9$ = $21$. $17$ with the two values swapped is $71$, and $17$ + $9$ + $9$ + $9$ + $9$ + $9$ + $9$ = $71$. Take the number $123$ and add $9$ a total ...
42
votes
13answers
7k 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, ...
42
votes
14answers
4k 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 ...
42
votes
0answers
1k views

Finding primes so that $x^p+y^p=z^p$ is unsolvable in the p-adic units

On my number theory exam yesterday, we had the following interesting problem related to Fermat's last theorem: Suppose $p>2$ is a prime. Show that $x^p+y^p=z^p$ has a solution in $\mathbb{Z}_p^{\...
39
votes
2answers
1k 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 ...
38
votes
13answers
11k views

Function which creates the sequence 1, 2, 3, 1, 2, 3, …

I was wondering how to map the set $\mathbb{Z}^+$ to the sequence $1, 2, 3, 1, 2, 3, \ldots$. I thought it would be easy, but I was only able to obtain an answer through trial and error. For a ...
38
votes
2answers
1k views

Is sum of digits of $3^{1000}$ divisible by $7$?

I'm working on a little exercise I found in my high school book (printed in 2007) which is pretty complicated. Is the sum of digits of $3^{1000}$ a multiple of $7$? Do you have any advice to solve ...
37
votes
1answer
3k views

Are prime numbers really random?

While practicing to code for my college course I stumbled upon this and would like to know if this is something new or significant as I haven't found anything resembling it on the internet. Let $p_i$ ...
35
votes
7answers
4k views

Why is there a pattern to the last digits of square numbers?

I was programming and I realized that the last digit of all the integer numbers squared end in $ 0, 1, 4, 5, 6,$ or $ 9 $. And in addition, the numbers that end in $ 1, 4, 9, 6 $ are repeated twice ...
35
votes
8answers
13k views

Why is $a^n - b^n$ divisible by $a-b$?

I did some mathematical induction problems on divisibility $9^n$ $-$ $2^n$ is divisible by 7. $4^n$ $-$ $1$ is divisible by 3. $9^n$ $-$ $4^n$ is divisible by 5. Can these be generalized as $a^n$ $-$...
33
votes
8answers
5k 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 ...
30
votes
6answers
12k 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?
30
votes
1answer
3k views

Can Mickey Mouse divide by $7$?

In the figure displayed in the image below : To find the remainder on dividing a number by $7$, start at node $0$, for each digit $D$ of the number, move along $D$ black arrows (for digit $0$ do not ...
30
votes
2answers
2k 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 ...
29
votes
6answers
3k views

Why do these days of the week line up?

I go to the gym every Mon/Wed/Fri while a friend of mine goes every 3 days regardless of the day. A typical two weeks could look like: ...
29
votes
5answers
8k views

Fibonacci modular results $\ F_n\mid F_{kn},\,$ $\, \gcd(F_n,F_m) = F_{\gcd(n,m)}$

Can any one give a generalization of the following properties in a single proof? I have checked the results, which I have given below by trial and error method. I am looking for a general proof, which ...
28
votes
17answers
50k views

How to Prove the divisibility rule for $3$

The divisibility rule for $3$ is well-known: if you add up the digits of $n$ and the sum is divisible by $3$, then $n$ is divisible by three. This is quite helpful for determining if really large ...
28
votes
4answers
7k views

Mathematics behind this card trick

Suppose I have $21$ playing cards. I distribute them in $3$ columns and tell you to choose mentally a card. Then just indicate in which column the card is. I pick up one of the columns which doesn'...
28
votes
2answers
766 views

An analogue of Hensel's lifting for Fibonacci numbers

Let $F_0, F_1, F_2, \ldots$ be the Fibonacci numbers, defined by $F_0 = 0$, $F_1 = 1$ and $F_n = F_{n-1} + F_{n-2}$ for all $n\geq 2$. In this question Oleg567 conjectured the following interesting ...
27
votes
4answers
2k views

Is a proof using modular arithmetic in a question like this valid?

It's been two years or so since I've finished my math undergrad (and I'm doing something non-math related now, unfortunately), so I apologize if what is to follow isn't a very good question! Prove ...
27
votes
2answers
635 views

Divisibility property for sequence $a_{n+2}=-2(n-1)(n+3)a_n-(2n+3)a_{n+1}$

Let $(a_n)$ be the sequence uniquely defined by $a_1=0,a_2=1$ and $$ a_{n+2}=-2(n-1)(n+3)a_n-(2n+3)a_{n+1} $$ Can anybody show (or provide a counterexample) that $p|a_{p-2}$ and $p|a_{p-1}$ for ...
26
votes
5answers
3k 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 ...
26
votes
2answers
5k views

Decoding Gauss' Easter Algorithm

In 1800, Gauss published this algorithm for computing the date of Easter in a given year $year$: $a = year \mod 19$ $b = year \mod 4$ $c = year \mod 7$ $k = \lfloor year/100 \rfloor$ $p =...
25
votes
13answers
4k views

Why do we use “congruent to” instead of equal to?

I'm more familiar with the notation $a \equiv b \pmod c$, but I think this is equivalent to $a \bmod c = b \bmod c $, which makes it clear that we should put a $=$ instead of $\equiv$. What's the ...
24
votes
6answers
14k views

If $n\ne 4$ 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. ...
22
votes
10answers
4k views

Shall remainder always be positive?

My cousin in grade 10, was told by his teacher that remainders are never negative. In a specific example, $$-48\bmod{5} = 2$$ I kinda agree. But my grandpa insists that $$-48 \bmod{5} = -3$$ ...
22
votes
4answers
40k 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?
22
votes
5answers
76k 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.
21
votes
1answer
510 views

What is the 2017th digit (from the right) of $2017^{2016^{2015^{\cdots^1}}}$?

What is the value of the $2017^{\rm th}$ digit starting from right side for $$ {2017^{2016^{2015^{\ldots 1 }}}}?$$ My attempt: $$2017^{n} \equiv x \pmod {10^{2017}} \quad \Longrightarrow \quad ...
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 ...
19
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 \,...
19
votes
2answers
3k 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 ...
18
votes
1answer
681 views

Flaw or no flaw in MS Excel's RNG?

I have a question about my understanding of an article of B.D. McCullough (2008) about Excel's implementation of the Wichmann-Hill random number generator (1982). First, a bit of context The ...
17
votes
5answers
4k 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, 377,...