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

Filter by
Sorted by
Tagged with
161
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 ...
100
votes
5answers
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 ...
96
votes
11answers
31k 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 ...
93
votes
9answers
12k 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, ...
87
votes
3answers
123k 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
84
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. ...
74
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 ...
67
votes
7answers
10k views

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

I don't know if this is a well-known 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 ...
62
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 ...
58
votes
7answers
144k 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 ...
45
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^{\...
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
5k 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 ...
39
votes
8answers
15k 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$ $-$...
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 ...
36
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
5k 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 ...
34
votes
9answers
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 ...
33
votes
17answers
55k 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 ...
31
votes
6answers
13k 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?
31
votes
2answers
799 views

Conjecture: Is $100$ the only square number of the form $a^b+b^a$?

Conjecture $100$ is the only square number of the form $a^b+b^a$ for integers $b>a>1$. In other words, $(a,b)=(2,6)$ is the only solution. Can we prove/disprove this? Observations The ...
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 ...
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 ...
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
4answers
8k 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
816 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
664 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
6k 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 ...
25
votes
6answers
15k 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. ...
24
votes
10answers
5k 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$$ ...
23
votes
4answers
45k 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?
23
votes
5answers
81k 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
520 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 ...
20
votes
0answers
401 views

Binomial coefficients modulo a prime

Consider an odd prime $p\equiv1 \pmod {16}$ and set $M=\frac{p-1}{2}$ for notational convenience. Then is there even a single prime $p$ of the above form for which the following congruence holds? $$\...
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 ...