# Tagged Questions

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

40 views

### $a^{100}-1$ is divisible by $1000$.

While working on competition math, I came upon the following problem: How many integers $x$ from $1$ to $1000$ are there such that $x^{100}-1$ is divisible by $1000$? This was very confusing, as the ...
92 views

69 views

### Determine: $13^{-1} \pmod {67}$

Determine: $13^{-1} \pmod {67}$ I'm not sure how to deal with the negative one here as it inverts the integer? Any help would be appreciated!
88 views

### Calculate: $16^{4321}\pmod{9}$

How to calculate: $16^{4321}\pmod{9}$ I think I have to use the Euclidean Algorithm for this or Fermat's Little Theorem but im really at a loss here. Anyone knows how to do this?
125 views

24 views

### Confused about a neither statement and modular

I am trying currently in the process of learning proofs involving congruence of integers with methods of direct and contrapositive and proofs with cases. However, I am quite confused by this statement ...
59 views

### Prove that $24^{31}$ is congruent to $23^{32}$ mod 19.

According to my knowledge, to prove that $24^{31}$ is congruent to $23^{32}$ mod 19, we must show that both numbers are divisible by 19 i.e. their remainders must be equal with mod 19. Please correct ...
45 views

### Can I apply Chinese remainder theorem here?

A number when divided by a divisor leaves $27$ remainder. Twice the number when divided by the same divisor leaves a remainder $3$. Find the divisor. My attempt: Let, the number be=$n$ and the ...
19 views

### Prove that if $ab \equiv cd \pmod{n}$ and $b \equiv d \pmod n$ and $\gcd(b, n) = 1$ then $a \equiv c \pmod n$.

Prove that if $ab \equiv cd \pmod{n}$ and $b \equiv d \pmod n$ and $\gcd(b, n) = 1$ then $a \equiv c \pmod n$. From this we know that $\gcd(d, n) = 1$. I can't derive anything else. Please help. Is ...
25 views

### Simple question about divisibility and modular arithmetic

Is the following true? Fix an $n\in \Bbb N$ which is not a multiple of $5$. Then for every $l\in\{0,\cdots,n\}$ there exists a $k\in \Bbb N_0$ with $5k\equiv l \mod n$. If yes, how do we prove it?
34 views

27 views

### Conditions for existence of quadratic residue congruent to 1

Under what conditions are we guaranteed an existence of quadratic residue 1 other than squares of 1 and -1. What conditions a number must satisfy to have such residue.
30 views

37 views

### Finding the digit in the units place [closed]

Find the digit in the units place of the number $2009!+3^{7886}$. The options available are: a) $7$ b) $3$ c) $1$ d) $9$
44 views

### simplifying a sum with modular arithmetic

Let $p\!\geq\!3$ be a prime and $n\!\in\!\mathbb{N}$. For $i\!=\!1,\ldots,n$ let $w_i\!=\!2i\!-\!n\!-\!1$. Let $n\%p$ denote the remainder in the integer division of $n$ by $p$. Can the following sum ...
20 views

### Proof that $t^m=t^{j}$ if $t$ is an $r^{th}$ root of unity such that $r \mid k$.

I need help with the following proof. Let $j$ = $0,1,\ldots, k-1$. Also, let $t$ be an $r$th root of unity other than $t=1$ such that $r \mid k$. We know $m=j\pmod k$. Furthermore, $m$, $j$ and $k$ ...
37 views

### Fermat's little theorem's proof for a negative integer

I'm in the process of proving Fermat's little theorem. For a prime integers $p$ we have $a^p \equiv a \mod{p}$ I proved it for a non-negative $a$, not I need to generalize the case to an ...
22 views

### Find modular arithmetic within a range.

When we execute any modular arithmetic say $a \pmod n$ then it results $0$ to $n-1$. But I need to find out a result within a range say $m$ to $n-1$. Is it possible? If then how?
22 views

### $2^i \equiv 2^j \pmod n$ implies $2^{j−i }\equiv1$ if $n$ is odd; also if $n$ is even?

Show that, if $0 \leq i < j$ and $2^i \equiv 2^j \pmod n$ and $n$ is odd then $2^{j−i} \equiv 1 \pmod n$. Is this necessarily true if $n$ is even? I have tried to prove this by using Fermat's ...
31 views

### How do you evaluate the quadratic residue of 7 mod p?

How do you evaluate this quadratic residue? I've been playing around with some specific values and I suspect 1 if p is of the form 28k+/-1, 3, 9 and -1 if 28k+/- 5, 11, 13. I have no idea how to come ...
33 views

### Find the modular arithmatic of mod p mod q.

I have an expression say $$x = ((a \bmod p) \bmod q)$$ Now given $x, p,q$, I need to find out the actual value of $a$. How can I do it? For an example I have: $$p = 109,\quad q = 26,\quad a = 171$$...
29 views

### Generating function for the Josephus Problem?

According to the Wikpedia article on the Josephus problem, the general solution is by dynamic programming. However, since there seems to be an explicit recurrence rule for the problem, should there ...