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$.
13,033
questions
0
votes
2
answers
348
views
Recursive Calls in Euclidean Algorithm
algorithm gcd(x,y)
if y = 0
then return(x)
else return(gcd(y,x mod y))
we're given this as the euclidean algorithm.
I get everything up to "so ...
1
vote
3
answers
70
views
Find the natural number $pq57r$ written in the decimal system , is divisible by $729$ then find $p,q,r$
Problem :
Find the natural number $pq57r$ , is written in the decimal system , is divisible by $729$ then find $p,q,r$
My attempt as following :
$\bar {pq57r}\equiv 0\pmod{729}$
$10000p+1000q+...
0
votes
2
answers
56
views
Is $(a \bmod N) \equiv (a \bmod x) \times (a \bmod y) $ where $x,y$ prime?
Can we say that for an $N$ where $N = xy$ and $x,y$ are prime
$$(a \bmod N) \equiv (a \bmod x) \times (a \bmod y) ?$$
1
vote
0
answers
48
views
Fast modular exponentiation $x^y \bmod 2^d$, $x$ is odd, $d\geq3$.
The task is to calculate $x^y \bmod 2^d$ in $O(d)$ summations/bitwise operations and 1 multiplication by $y$. The number $x$ is odd, $d\geq3$.
I've found the proof that $x^{2^k} \equiv 1 (\bmod 2^{k+2}...
10
votes
2
answers
453
views
Is the finite sum of factorials constant modulo the summation limit?
The answer to the following question would give an alternative solution to an old olympiad question if it is true.
Prove that there is no (constant) integer $c$ such that
$$1!+2!+\dots + q! \equiv c ...
3
votes
1
answer
931
views
Question about congruence classes and reduced residue systems
Let $x$,$y$ be integers such that the reduced residue system modulo $y$ divides equally into congruence classes modulo $x$.
An example of this is $x=4$, $y=5$.
The reduced residue system modulo $5$ ...
2
votes
2
answers
60
views
Find $a\in\Bbb Z$ such that $a^3\equiv 3 \pmod{11}$ without Fermat or Euler.
Find all $a$ integers such that $a^3\equiv 3 \pmod{11}$
I have this problem and I can't use Fermat or Euler theorems because we haven't seen them in class. I also have a solution that I don't ...
2
votes
0
answers
260
views
Show that $\phi$ is a homomorphism using modular arithmetic
The following proof should show that $\phi$ is a homomorphism, by making use of a modular arithmetic property:
\begin{equation}
(A+B) \mod {C} = (A \text{ mod C} + B \text{ mod C}) \mod {C}
\end{...
0
votes
0
answers
14
views
Solutions of this set of linear congruences using Chinese Remainder Theorem? [duplicate]
Suppose m1, m2, ..., mk are positive integers > 1, not necessarily pairwise relatively
prime. Also Suppose a1, a2, ..., ak ∈ Z. What can be said about the solutions of the following set
of linear ...
3
votes
1
answer
372
views
Arithmetic inequality comparison of integers in residues modulo primes
Consider arbitrary precision integers $a, b$ represented in residue form modulo a set of primes $\{ p_0, p_1, \dots, p_n \}$. We can represent very large integers by increasing the number of prime ...
-1
votes
1
answer
31
views
find if any number in A.P can be divided by a given number(k).
If there is any method other than finding each number of A.P iteratively and check if it is divisible by k or not?
Example :
Tn = 11*n+d;
k = 7;
find if (Tn % k == 0) ?
1
vote
0
answers
34
views
Show that $n$ can be written in the form $n=c_{0}+c_{1}d+...+c_{k}d^{k}$ [duplicate]
I day ago, i've been solving some induction exercises from my textbook. But when i saw this, it seems a bit tricky and i couldn't come up with a solution. I hope someone can give clarity for this. ...
1
vote
1
answer
495
views
Solving Quadratic, Cubic and Higher Degree Congruence Equations
I have a question about solving polynomial equations modulo some number.
Say we were to solve the following quadratic congruence equation:
$$x^2+x + 2 = 0 \quad mod \quad 4$$
We could of course just ...
3
votes
2
answers
751
views
Show that mod-function is surjective
We are to show that the following function is surjective, when n is from the set of integers: $$(4n+6)mod(1729)$$
The codomain are the integers from {0, 1728}
How do I proceed?
In advance, thank you ...
4
votes
6
answers
780
views
$4x≡2\mod5$ can you divide both sides by $2$ to get $2x≡1\mod5\,?$
Since gcd$(2,5)=1$ , could you treat $4x$ as $2(2x)$ and cancel the $2$ on both sides?
i.e. $$2(2x)≡2\mod5\implies 2x≡1\mod5$$
Thanks!
1
vote
0
answers
49
views
Solving an or (linear) congruence system
Usually, when we solve a congruence system, we try to find the general solution that fits the first equation and the second equation and the third, and so on.
How should we solve a congruence system ...
2
votes
2
answers
3k
views
How to combine congruences?
I have two congruences:
$$ \text{(i) }p\equiv 1 \mod 3 \,\,\, \land \,\,\, p\equiv 1 \mod 4 \\
\text{(ii) }p\equiv 2 \mod 3 \,\,\, \land \,\,\, p\equiv 3 \mod 4
$$
Is it possible to write these ...
2
votes
2
answers
12k
views
Prove that $ ab \bmod n = (a \bmod n) · (b \bmod n) $
Written in Abstract Algebra by T. W. Judson, in an example in the theory of rings it supposes (without proof) that:
$$(a+b) \bmod n = (a \bmod n) + (b \bmod n) $$
and
$$ ab \bmod n = (a \bmod n) · (b \...
1
vote
1
answer
68
views
Quadratic residues short proof
I'm not too sure how to answer this question here, so if someone could help me out, that'd be great.
Super $m$ is odd and $a$ and $m$ are coprime. Show that
$ax^{2} + bx + c \equiv 0 $(mod $m)$
has an ...
0
votes
3
answers
62
views
Is this a correct mathematical statement about integers mod n and congruence mod n? [closed]
Let's say we have the congruence: $b \equiv a \mod 20$
Is it then correct to say that $(b \equiv a \mod 20 )= \mathbb{Z}_{20}$
where $\mathbb{Z}_{20}$ is the set of residue classes or set of ...
1
vote
1
answer
72
views
Is exactly one of $a, a + b^n, ..., a + b^{p - 1}$ divisible by $p$?
Consider the following structure over $\mathbb{N_0}$: $2, 2 + 3^n, 2 + 3^{n + 1}, ..., 2 + 3^{n + 3}$. Here we have five numbers and it's not hard to prove that exactly one if them is divisible by $5$....
3
votes
4
answers
260
views
Role of coprimality in proof of Fermat's Little Theorem
This is the start of the proof for FLT:
I was curious -- I know that all the elements of S are unique because gcd(a,p) = 1, but I was wondering --
What would be an example in which the elements were ...
2
votes
3
answers
70
views
How can I find a prime that satisfies these two congruences?
Hi I was solving a question and now I'm stuck at this part .
$-6x\equiv 16 \pmod p $
$2x\equiv 1 \pmod p $
where $p$ is a prime number.
I need to find all prime numbers that satisfy these ...
0
votes
1
answer
49
views
How to prove that $2^n \equiv n \pmod p\:$ iff $n=(p-1)(kp-1), k \in \mathbb{Z}$?
Okay, I am solving equivalence $2^n \equiv n \mod p$ for $n \in \mathbb{N}$ and odd prime $p$.
I got that if $n = (p-1)(kp-1)$ then we have a solution (using Fermat's little theorem)
But is it true ...
0
votes
2
answers
84
views
Prime divisors of $x^{16}+1$ [duplicate]
$x \in Z$. Prove, that all prime divisors of $x^{16}+1$, which are not equal to 2, are equal $1 \pmod{32}$.
0
votes
1
answer
83
views
Is there a way to generalize clock algebra? [closed]
As in the difference between $9$ o'clock am and $5$ o'clock pm is $8$ hours. I thought working in mod $12$ would work but that only seems to work for addition as in:
$$9+8=17$$
And $17$ mod $12$ is $5$...
2
votes
3
answers
50
views
How does one get from $p+3=3k+2$ then $2^{p+3} \equiv 4 \pmod 7$, to $5 \cdot 2^{p+3} -31 \equiv 3 \pmod7$
How does one get from $p+3=3k+2$ then $2^{p+3}\equiv4 \pmod 7$, to $5 \cdot 2^{p+3} -31 \equiv 3 \pmod7$.
I am just starting with modular arithmetic so any help would be greatly appreaciated.
Credit ...
0
votes
2
answers
51
views
Modulo arithmetic: finding “c” when result of right-hand side expression is a float [duplicate]
In my series of questions on modular arithmetic, I stumbled upon cases where normal textbooks don't explain much.
Now my problem is to find $c$ when the expression to be solved (right-hand side) ...
-1
votes
2
answers
64
views
Two versions of Eulers theorem and how they relate. [duplicate]
I am familiar with the following Euler Theorem: (Note: In the following ø(n) is the Euler function)
version i)
If gcd(x,n)=1, then $x^{ø(n)} = 1$ (mod n).
Version ii) However, I have seen the ...
0
votes
1
answer
65
views
Prove that there is no permutation of the first n naturals satisfying a condition such that every sum of 4 consescutive terms is equal to 1 mod 2.
Given a set $\left ( 1, 2,3,...,n \right )$ where $n>5$ , I want to show that given all permutation $p$ $\left ( \sigma \left ( 1\right ), \sigma\left ( 2\right ),\sigma\left ( 3 \right ),...\...
1
vote
1
answer
41
views
Is exponentiation to a modulo equivalence preserved?
That is, if $a = b \pmod n$. Will it be true that $x^a = x^b \pmod n$? If this is true, how can I prove this? Thanks,
1
vote
1
answer
37
views
Modula computation with a oracle
Assume we have unknown number $d$ and an oracle which can tell us in one step if for any residual $x$ the equation $(1)$ $d \equiv x \textrm{ mod } p$ , with $p$ prime, holds.
The important thing here ...
0
votes
0
answers
65
views
$2^a$ divides an expression for any value of a
show that we can get an "$x$" for every "$a$" such that
$15^2(15^x-5^{x-2}-3^{x-2}) \equiv -1 \pmod{2^a}$
0
votes
0
answers
60
views
Proof $P_{n}(7) ≡ 0 \pmod {19}$ for every $n∈N$ given $P_{n}$ formula
Given
$$P_{0} = x + 12 $$
$$P_{1} = x^2-5x+5$$
$$P_{n} = xP_{n-2}(x) - P_{n-1}(x) $$
Prove $P_{n}(7) ≡ 0 \pmod {19}$ for every $n ∈ N$
And prove for every prime q, if $P_{2017} (x)$ is not congruent ...
2
votes
1
answer
136
views
Show that there exists infinitely many primes which satisfy a given congurence.
Let $m$ be a fixed positive integer that is the product of distinct prime factors of the form $(3k+2)$, such as $5 \times 11$.
Prove that there exist infinitely many primes $p$ such that $3^{3p-2}\...
0
votes
0
answers
90
views
How to prove that these groups are isomorphic (or not)?
I have these following groups.
($\mathbb{Z}/14\mathbb{Z},+) \times(\mathbb{Z}/15\mathbb{Z},+)$ and $(\mathbb{Z}/10\mathbb{Z},+) \times (\mathbb{Z}/21\mathbb{Z},+)$
($\mathbb{Z}/13\mathbb{Z}\...
0
votes
0
answers
2k
views
If $p$ is a prime, then $(p-1)! \equiv -1 (mod p)$ [duplicate]
If $p$ is a prime, then $(p-1)! \equiv -1 (mod p)$. Hint: $(p-1)!$ is the product of elements in $Z_p$. Match each element to its inverse.
I can understand by testing some primes that for any prime $(...
-1
votes
2
answers
468
views
List all the numbers which have an inverse MOD 20 [duplicate]
Please help! I’m not sure where to start. I really need someone to thoroughly explain how to do this.
0
votes
0
answers
82
views
How to find remainder of $31^{41^{101}}$ from division by 53? [duplicate]
When we see such a big and difficult to calculate number, we want to use Fermat's little theorem (especially when we see prime number as divider)
But how do we approach situation when we have number ...
1
vote
2
answers
405
views
FInd the missing digit in $2^{29}$ given all nine digits differ
The number $2^{29}$ has (in base $10$) $9$ digits, all different. Which digit is missing?
I think about using fermats theorem dosen't know how to begin
2
votes
0
answers
96
views
How do I prove 8(x)! + (2x-1)² where x is an integer greater than or equal to 3, is never a perfect square.
$8(x)! + (2x-1)^2 = a^2$, so $8(x)! = a^2-(2x-1)^2$, for $x \geq 8$, $64|\text{LHS}$, but we can see 8 doesn't divide both of $(a-2x+1)(a+2x-1)$, so 64|one of them, so both one of them is $0 \pmod {64}...
0
votes
2
answers
62
views
Modulo arithmetic: finding "c" when there is a number attached to it [duplicate]
I am fairly new to number systems and notations. I have a problem where I need to find $c$ in:
$13c ≡ 27a − b^{3} \mod (43)$ given that $0 \leq c < 43$.
Also, $a ≡ 27 \mod(43)$ and $b ≡ 19 (\mod 43)...
2
votes
5
answers
3k
views
Proving that among any $2n - 1$ integers, there's always a subset of $n$ which sum to a multiple of $n$
How can one prove that among any $2n - 1$ integers, there's always a subset of $n$ which sum to a multiple of $n$?
It is not hard to see this is equivalent to show that among $2n-1$ residue classes ...
4
votes
3
answers
552
views
infinitude of primes that are $11 \bmod 12$
Suppose there are finitely many primes $\{p_1, \ldots, p_k\}$ which are $11 \pmod {12}$ and consider $p = (p_1 \cdots p_k)^2 + 10$. Then $p_i \nmid p$ for any $i \leq k$, and $p \equiv 1 + 10 \equiv ...
4
votes
1
answer
119
views
Numbers $+1$, $-1$ on a circle.
Let $n$ be a positive integer and that $2n$ numbers are arranged at different points around a circle, half of these numbers being $+1$ and half of being $-1$. Moving clockwise around the circle from a ...
1
vote
1
answer
292
views
Can't understand the solution of this INMO problem
In any set of $181$ square integers, prove that one can always find a subset of $19$ numbers, sum of whose elements is divisible by $19$.
Someone on AOPS:
Direct checking shows that any square is $0,...
-1
votes
2
answers
50
views
Modular arithmetic: finding "c" when it is an exponent [duplicate]
I am fairly new to number systems and notations. I have a problem where I need to find $c$ when it is an exponent:
$a ≡ b^{c} \mod 43$ given that $0 \leq c < 43$ and,
$a ≡ 27 \mod 43$ and $b ≡ 19 \...
0
votes
1
answer
2k
views
Given n integers, show that there is a subset whose sum is divisible by n. [duplicate]
I’ve tried this.
Let the integers be $a_1, a_2,...,a_n$.
On dividing any number by $n$, we have $n$ possible remainders which are $0,1,2,...n-1$. Let these $n$ remainders be $n$ pigeonholes.
From the $...
-1
votes
2
answers
61
views
Help with proving this mod statement [duplicate]
$$\forall x, y, n \in \mathbb{Z}, x=y \ \implies x \equiv y\ (mod\ n)\ $$
I am not sure if I am doing this properly and I don't know if I can show my proof like this:
Suppose x = y which means x = ...