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

Modular arithmetic (clock arithmetic) is a system of arithmetic of integers. The basic ingredient is the congruence relation $a \equiv b \bmod n$ which means that $n$ divides $a-b$. In modular arithmetic, one can add, subtract, multiply, and exponentiate but not divide in general. The Euclidean Algorithm, the Chinese Remainder Theorem, and Fermat's Little Theorem are important throughout mathematics. Modular exponentiation plays an important role in cryptography nowadays.

11320 questions
3
votes
0 answers

A question from an old french olympiad

I've found an exercice that I've no clue to do it, I expose it to you Let suppose we have a family of $1789$ integers which sum is equal to zero. Show that the sum of their $37$th power is a multiple of $399$. Any hint or solution ?
Atmos
  • 7,369
3
votes
2 answers

Solving cubic congruence

I wasn't actually taught about cubic congruences equation and was managing with quadratic congruences until I was hit with this: $$x^3 \equiv 53 (\text{ mod } 120)$$ Effort: I tried deconstructing it into a system of congruence equation assuming…
Liam
  • 33
3
votes
2 answers

Modular arithmetic and some applications

Show that if $p> 2$ is a prime number, then $p$ divides $(p-2)! - 1$. I have tried using Fermat's Theorem, but I could not solve it.
3
votes
2 answers

Understanding powers of an element

For example we have: $$ \begin{aligned} \mathbb{Z}_7^* &= \left\{[z]_7 \in \mathbb{Z}_7 : \gcd(z, 7) = 1, 1 \leq z < 7, \forall z \in \mathbb{Z}\right\} \\ &= \{1, 2, 3, 4, 5, 6\} \\ \left &\in \mathbb{Z}_7^* : \{a^b \mod 7: \forall a,b…
Drew
  • 155
3
votes
0 answers

Modular Arithmetic Problem given two variables

Let $x$ be the smallest positive integer so that there exists at least $10$ values of $y$ such that $xy^{2}+1$ has at least two factors congruent to $-1$ mod $y$. Find the remainder when $y$ is divided by $1000$. $\textbf{Thoughts}$ First of all, I…
Kit_Kat
  • 255
3
votes
4 answers

Fermat's little theorem confusion

Problem, What is the remainder when $3^{50}$ is divided by $7$ I know I have to use Fermat's little theorem, but I'm confused at a certain point. I have that $3^{6}\equiv1 \bmod7$ Now I'm not sure what to do, although I know that the remainder is…
3
votes
1 answer

Basic modular inverses

I know how to do modular inverses in a hypothetical sense with the Euclidian method, and have been trying to do the, but I seem to keep getting the incorrect answer. I'm trying to find the inverse of $\;5\pmod {13}$, for example. The answer…
jacksonf
  • 526
3
votes
5 answers

Proof using Mod

How can you prove that: $$a^7\equiv a\:(\text{mod } 42)$$ I haven't been given any other information other than to use Fermat's theorem.
Sam
  • 431
3
votes
2 answers

Find $r$ where $\dfrac{(7n)!}{7^n n!} \equiv r \pmod{7}$, $r \in [[0, 6]]$

I conjecture that: $\begin{equation*} \dfrac{(7n)!}{7^n n!} \equiv \left\{ \begin{aligned} & 1 \text{ if } n \text{ is even} \\ & 6 \text{ if } n \text{ is odd} \end{aligned} \right. \pmod{7} \end{equation*}$ Based on hand observations. I tried to…
Raito
  • 1,890
  • 11
  • 17
3
votes
2 answers

Linear combinations of two numbers can only be multiples of their gcd?

If we are on a number line starting at 0 and we can only take steps x or y long in either direction where x and y are integers, we can only reach points that are (integer) multiples of gcd(x, y). Apparently this is true, but I am having a hard time…
3
votes
2 answers

What is the remainder when dividing $11^{(345^{678})}$ by 13?

So basically I figured out that this problem comes down to the following: We want to find the answer to $11^{(345^{678})} \ \text{mod} \ 13$. Then, because $11$ and $13$ are coprime, we know that $11^{\phi(13)} = 1 \ \text{mod} \ 13$. Because 13…
ArianJ
  • 670
  • 5
  • 21
3
votes
5 answers

Find the smallest positive integer satisfying 3 simultaneous congruences

$x \equiv 2 \pmod 3$ $2x \equiv 4 \pmod 7$ $x \equiv 9 \pmod {11}$ What is troubling me is the $2x$. I know of an algorithm (not sure what it's called) that would work if all three equations were $x \equiv$ by using euclidean algorithm back…
Arvin
  • 1,733
3
votes
0 answers

Solving $2\times 2$ system of congruence using elimination

Let us suppose we have following system $${5x+7y}\equiv 3\pmod {9}.$$ $${6x+5y}\equiv 4\pmod {9}.$$ I need to solve this task using elimination, first let us eliminate $y$ term, for this let us multiply first equation by $5$ and second one by…
3
votes
4 answers

How to convert $0$ to $1$ and any whole number greater than Zero to $0$?

I am stuck on converting $0$ to $1$ and any whole number greater than Zero to $0$. Is there a mathematical way for doing so?Also how to notate it when using it in a function?
3
votes
1 answer

Why is $5^{25} \equiv 22 \mod 193$

I'm trying to apply the square and multiply algorithm and I'm getting strange results even though I'm pretty sure I've done everything right. I'm trying to calculate $5^{25} \mod 193$: Binary representation of 25:…
AdHominem
  • 153