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
1
vote
2 answers

How can I solve these Modular problems?

Very basic question, but how can I solve this? $7x+9y \equiv 0 \bmod 31$ and $2x-5y \equiv 2 \bmod 31$.
user82004
1
vote
3 answers

Approaching modular arithmetic problems

I'm a little stumbled on two questions. How do I approach a problem like $x*41 \equiv 1 \pmod{99}$. And given $2$ modulo, $7x+9y \equiv 0 \pmod{31}$ and $2x−5y \equiv 2 \pmod{31}$ (solve for $x$ only)? When I solve for $x$ for the latter, I got a…
whatdidthefoxsay
  • 111
  • 1
  • 1
  • 7
1
vote
1 answer

Diophantine equations in relation to modular arithmetic

Here are some of the known definitions: $$a \equiv b \pmod m$$ $$a -b =km \Rightarrow a=km+b$$ Now we also have: $$ax = b \pmod m \Rightarrow ax+my=b$$ I'm having a little trouble relating all of this because if we take for example: $3x \equiv…
Dimitri
  • 1,287
1
vote
4 answers

Finding $a^n \bmod b$?

What is a good algorithm for finding the remainder? For example: What would be the algorithm for finding the solution of $103^{45} \bmod 5$?
Don Larynx
  • 4,703
1
vote
2 answers

Converse of Fermats Little Theorem generalization hold true?

For the generalized form of FLT, assuming m and n are positive integers and p is prime, if $m \equiv n \pmod {p - 1}$ then for every $a$, $a^m \equiv a^n \pmod p$. Is the converse True, such that for every $a$, $a^m \equiv a^n \pmod p$ it must hold…
TheoretiCAL
  • 185
  • 5
1
vote
1 answer

Find the remainder when $(1! \times 1) + (2! \times 2) + (3! \times 3) + \cdots + (100! \times 100)$ is divided by $101$.

I'm faced with a difficult problem that I can't prove. The problem is stated as: Find the remainder when $(1! \times 1) + (2! \times 2) + (3! \times 3) + \cdots + (100! \times 100)$ is divided by $101$. I found a pattern which is $(1! \times 1) +…
1
vote
0 answers

Trialdivision for Proth's numbers

I want to test Proth's numbers for primality. These are numbers of the form $h\cdot 2^k+1$ for a natural $k$ and an odd $h<2^k$. I am wondering whether I can find a faster method than the "normal" trialdivision. So my thought is: Let $p$ be an odd…
Lereu
  • 424
1
vote
1 answer

What are the last three digits of the number $p= 2^{216091}-1$

Prove that the prime number $p = 2^{216091} - 1$ has the last three digits equal to 447. I have this answer below, but I cannot fully understand the reason for the two congruences made: the module 8 and the module 125. Additionally, I don't…
emacos
  • 249
1
vote
0 answers

Prove $2^x \equiv 1\bmod 7 \iff x\equiv 0\bmod 3$

I recently did a coding challenge which asked for all numbers $n$ in a range which fulfill: $n = 2^x$ $n = 1\bmod 7$. By playing around my impression is that $2^x \equiv 1\bmod 7 \iff x\equiv 0\bmod 3$. The assumption certainly held for the ranges…
1
vote
1 answer

Questions on a new method to find the remainder of the division of $1009^{12}+1$ by $2017$?

I tinkered with this method to calculate the remainder of a division you can see the examples, and the questions I ask myself are: Question 1: In what case is this method better than other methods for finding the remainder of the division. Question…
z.10.46
  • 27
  • 5
1
vote
1 answer

Deriving modular properties of factors of a polynomial based on the roots of the polynomial.

This is from an answer by Robert to this question When are $n!+1$ and $(n+2)!+1$ coprime? "The roots of $x^2 + 3x + 1$ are $(-3 \pm \sqrt{5})/2$, so $5$ must be a square mod $p$, which says (if $p > 5$) $p \equiv 1$ or $4 \mod 5$." Can anyone…
1
vote
0 answers

Is it true that if $a\equiv b \pmod m$ then $am\equiv bm \pmod{m^2}$?

Just what the title says, I have searched but haven't found anything, either for yes or no. Does somebody know? My reasoning is: $a \equiv b \pmod m$ $\implies a = b + mk$, for some $k$ $\implies$ multiply both sides by $m$ and I get $am = (b +…
G25
  • 19
1
vote
1 answer

Solving quadratic congruence

How to solve congruence $x^2-2 \equiv 0\pmod a$, $x$ and $a$ are integers, and $a$ mustn't be prime? I have found solution when a is prime, but I haven't found solution for general case.
1
vote
1 answer

Extending the usefulness of xor for identifying items not in a sequence.

Given the sequence [0 .. 255] If a single value is removed, the xor of the remaining values produces that missing value. However, if two values are removed, This no longer works. A. Why does this happen for the single-value case? B. Can this be…
1
vote
1 answer

How to describe a modulo operation in spoken words

Several of the basic arithmetic operations can be described in spoken words such as: $x + y$ - Add $y$ to $x$ $x - y$ - Subtract $y$ from $x$ $x \times y$ - Multiply $x$ by $y$ $x \div y$ - Divide $x$ by $y$ I'm wondering if there is a similar way…
kuenzign
  • 113