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

Filter by
Sorted by
Tagged with
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 = ...

1
59 60
61
62 63
261