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

9,808 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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 ...
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, ...
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
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. ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
1k views

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 ...
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. ...
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$$ ...
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?
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.
520 views

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 ... 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 ... 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?$$\...
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 \,...
### 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 ...