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

Prove that there are no integers $x$ and $y$ such that $x^2 = 5y + 2$

Should I use the Division Algorithm to solve this or investigate 4 cases in which either x or y is even/odd or they are both even and odd? I don't think my instructor would accept the latter. Thank you.
Uyen Le
  • 49
1
vote
0 answers

Counting congruence classes

I am trying to understand the methods to count congruence classes, typically like$\def\mod{\operatorname{mod}}$ $$\sum_{\substack{x \mod N \\ nx \equiv m \mod d}} \!\!\!\!\!1$$ I would like to assume there is no conditions on $N, n$ and $d$.…
Amomentum
  • 375
1
vote
2 answers

Modular arithmetic and inverse functions

The question is shown below: Suppose $S=\{0,1,2,3,4,5,6,7,8,9,10\}$ and that the function $f:S\rightarrow S$ is given by: $f(x)=6x^2+3x+8$ (mod 11) Let $T=\{0,5\}$. Find $f^{-1}\left(T\right)$. Alright, so my initial approach with this question was…
Steve
  • 13
1
vote
1 answer

Equivalent modulos

In my course notes I came onto two examples for finding remainders of huge numbers with fermat's little theorem and need some helping analyzing them. 1) Find the remainder when 5^183 is divided by 11. I know that 5^10 ≡ 1 mod(11) so (5^(10*18))…
Michael
  • 397
1
vote
1 answer

Find the modulo between two large number

I'm trying to find 3185^2753 mod 3233 to decode a RSA message. How can I do it? What is the theorem behind this, if any? The original question is: What is the original message encrypted using the RSA system with n=53·61 and e=17 if the encrypted…
Chin
  • 323
  • 2
  • 6
  • 15
1
vote
0 answers

Can RSA encrypt infinitely many messages?

In RSA encryption, a message $m$ encrypted using a public key $(n,e)$ and decrypted by private key $d$, according to following relation (where $c$ is encrypted data); $c = m ^ e (\mod n)$ $m = c^d (\mod n)$ Am I correct to think that encrypted value…
yasar
  • 237
1
vote
2 answers

How to find cube roots of 1 modulo power of two (if they exist)?

It would be useful for efficiently implementing an algorithm if I could find a $c > 1$ where $c^3 \equiv 1 \pmod {2^{64}}$. It's plausible that such a $c$ exists because $2^{64} \equiv 1 \pmod 3$, so all non-zero values could be partitioned into…
1
vote
2 answers

Show no solutions exist for $x^3 + y^3 = 7777781.$

For the following equation $$x^3 + y^3 = 7777781$$ we have to prove no solutions exist. How to go about this? Will it require a modular arithmetic property?
user737542
1
vote
1 answer

Prove that if $~(n)|m~$ then $~a^m ≡ 1(\mod n)~$

Prove that if $~(n)|m~$ then $~a^m ≡ 1(\mod n)~$ I'm finding this hard for me to prove, I would more than appreciate help with this. $~\gcd(a,n)=1~$; $~a,n,m∈\mathbb N~$ this is all I'm given, how do I do this? Thank you very much for all the help
1
vote
2 answers

Inverse with Fermat, Modulo

I wonder about an equation given as a solution to the following task: Calculate the multiplicative inverse $$5^{−1} \pmod {13}$$ The solution ends in this equation: $$ 5^{11} \equiv 5^{10} \cdot 5 \equiv −1\cdot 5 \equiv 8 \pmod {13} $$ and…
yesyoor
  • 13
  • 3
1
vote
3 answers

System of congruences with variable

I am looking over 2013 AMC 10B Problem 25, and I came across a solution containing this: Problem Bernardo chooses a three-digit positive integer $N$ and writes both its base-5 and base-6 representations on a blackboard. Later LeRoy sees the two…
mpnm
  • 1,097
1
vote
1 answer

I can't determine the maximum natural number which is unable to be represented as $17\times x+23\times y$

The given problem is the following one. Find the maximum natural number which is unable to be represented as $17\times x +23\times y \quad x,y\in \mathbb{N}$ . I've been solving it till following formulas with looking the solution of the…
user738488
1
vote
1 answer

I need to determine the values of $a$ and $b$ such that $a-b=33333$ with using $9$ cards ($i$-th card represents $i$).

$9$ cards are given ($i$-th card represents $i$) and $2$ following numbers are defined by using all $9$ cards. $a:=5$ digits natural number which are given by concatenating $5$ cards. $b:=4$ digits natural number which are given by concatenating $4$…
user738488
1
vote
0 answers

Converse of Fermat's Little Theorem

Fermat's little theorem states that if $p$ is prime, then $\forall a\in\mathbb N \quad a^p\equiv a \quad \text{mod} \quad p$. Is the converse true ?
James Well
  • 1,209
1
vote
1 answer

Explain negative modulo like I'm five?

I know this has been addressed here, but I confess to not fully understanding that, so I'm hoping someone can chime here. First, is there a canonical formula for this? In programming language languages, different ones lead to varying results, which…