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

learn more… | top users | synonyms

0
votes
0answers
7 views

Find interval algorithm problem

I have the following arithmetic problem: What is known condition: m,n [a,b) : a mod(m) = 0 , b mod(m) = 0 [x,y) : x mod(n) = 0 , y mod(n) = 0 b < x What must ...
0
votes
0answers
26 views

Let $n\in \mathbb{N}$ and $p>2$ a prime number show that $(1+p)^{p^n} \equiv 1+p^{n+1} \ [p^{n+2}]$

I tried an induction on $n$ : For $n=0$, we obtain : $1+p \equiv 1+p \ [p^2]$ it is right ! For $n=1$, I get : $(1+p)^p = \sum \limits_{k=0}^p \binom pk p^k$ and I noticed that for $k\in ...
0
votes
1answer
16 views

Finding other solutions to diophantine equations

I understand how to find the first solution to these equations but can't grasp how the other solutions are found. E.g. $102x\equiv 12 \pmod{174}$ So I can find the $gcd(174,102)=6$ (showing that ...
0
votes
1answer
31 views

How to find $n$ if $a^n \equiv r \pmod m$

In particular I'm looking at the problem: \begin{align*} 3^{n_1} &\equiv 1 \pmod 4 \\ 5^{n_2} &\equiv 1 \pmod 4 \\ 7^{n_3} &\equiv 1 \pmod 4 \\ \end{align*} And I want to find $n_1, ...
-1
votes
1answer
62 views

5-digit square has sum not 29. [closed]

Show that there is no five-digit number is a square number . where the sum of his digit is 29 , I tried to solve this question more and more , But , I didn't get any solution . I hope I can ...
1
vote
1answer
38 views

Show that every number $a$ can be shown in the following form: $a=\sum_{i=1}^{k}2^{x_i}\cdot 3^{y_i}$

Show that every integer $a>0$ can be shown in the form: $$a=\sum_{i=1}^{k}2^{x_i}\cdot 3^{y_i}$$ where $0\le x_1< x_2< \dots < x_k$ and $0\le y_k < y_{k-1} < \dots < y_1$ are ...
0
votes
3answers
90 views

Proof that $(3\cdot 2^n-1)$ is not a multiple of $17$ for any value of $n$ [closed]

Prove that $3\cdot 2^n-1$ is not a multiple of $17$ for any positive integer $n$.
1
vote
1answer
25 views

Sequence of remainders of multiples

I am interested in the sequence of remainders of the integers $kp$ when divided by $q$, with $\gcd(p,q)=1$. For instance, with $p=7,q=17$, ...
1
vote
0answers
33 views

ab = X mod Y (X and Y known)

Is there a better way to determine possibilities for $a \mod Y$ and $b \mod Y$ in the following equation: $ab = X \mod Y$ than by brute force? For example if $ab = 5 \mod 6$ then either $a = 1 \mod ...
0
votes
2answers
49 views

Congruence for large modulus

The idea it to find remainder $35^{32} + 51^{24} \bmod 1785$. 1785 is a composite number equal to 3 x 5 x 7 x 17. 35 is 0 mod 5 and mod 7. 51 is 0 mod 3 and mod 17. Any help regarding steps from ...
-1
votes
1answer
38 views

Prove x and p are coprime

Let $x$ be an even integer and p=$x^{4}+1$. $p$ being a prime divisor How can I prove that $x$ and $p$ are co-prime to one another. Also that $x$ is invertible modulo $p$. Would I assume ...
0
votes
1answer
25 views

Last four digits of a perfect square [closed]

If the last four digits of a perfect square are the same, then prove that the four digits must be $0$.
0
votes
0answers
17 views

Distribution of numbers from a cyclic group $Z_p$

Let assume, that I have a group of prime order $p-1$ denoted as $Z_p$. From this group I generate randomly two sets of numbers: $\{x_1, x_2, x_3, x_4, x_5\}$ and $\{y_1, y_2, y_3, y_4, y_5\}$ and ...
1
vote
1answer
14 views

Polynomial Residue Classes

Let $g(x) \in \mathbb{F}[x]$ be a polynomial of degree $\geq 1$. The residual class of $a(x) \in \mathbb{F}[x]$ modulo $g(x)$ is the set. $ \overline{a(x)} = \{b(x) | b(x) \equiv a(x) \mod g(x) \} ...
1
vote
1answer
17 views

A “simple” question about the order of subgroups of the group of additive integers

Simple, but I cannot answer it. Let $\mathbb Z_n$ be the additive group of integers with order $n$. Suppose $m$ is a factor of $n$. Then $\mathbb Z_n$ contains a subgroup of order $m$. I am trying ...
1
vote
1answer
33 views

Prime and Repunits

Prove that: For any integer $n > 5$, if $n$ divides $\dfrac{10^{n-1}-1}{9}$, then $n$ is a prime number. This can also be generalized further as If $n$ is an integer > 5 and divides a ...
-1
votes
0answers
19 views

Arithmetic problems with understanding

I'm having problems with understanding qn 22. Part (III) don't really know what are they asking :|
1
vote
1answer
12 views

Ensure that for each number in specific space there is inverse

Let say I want to find the Inverse number of some serial number. ( 9 digits number .. its can be an ID). And let say we want to find the inverse in $\mathbb Z_{1000000123}$ ( for example ) How I can ...
0
votes
1answer
27 views

find smallest number $M$ for which the remainder of $N/M$ is equal to $3$

given a positive integer $N$ greater than $3$, is there a smart or algorithmic way to find the smallest number $M$ for which the remainder of $N/M$ equals $3$? one obvious answer is always $N-3$, but ...
1
vote
1answer
27 views

Solving a modular exponentiation problem

How do I solve for $y$ in this congruence: $$11^{112111} \equiv y \bmod 113$$ I saw that $113$ is prime and so by Fermat's Little Theorem, it means $a^{112} \equiv 1 \bmod 113$. $$11^{112111} ...
2
votes
1answer
28 views

Stuck with the statement: $t^4+2$ in $\mathbb{Z}_5$ gives rise to…

This is from Ian Stewart's book on Galois theory, I am looking at irreducible polynomials. It talks of irreducibility over mod. It takes as an example, $f(t)=t^4+15t^3+7$ over integers, and asks us ...
0
votes
2answers
42 views

Find $x \in{Z_{250}}$ so that $ x\equiv{248^{156,454,638}} \pmod{250}$?

I am looking for a easy way to solve it, without use the computer. I did that but with the computer. $GCD(250,248) \ne 1$ So I did: $250 = 125*2$ $248^{156454638}$ (mod 250) = $248^{156454638}$ ...
0
votes
2answers
22 views

Quadric modular equation

I had to calculate $x$ from $x^2 =x\pmod{10^3}$ I knew that $a = b\pmod{cd} \Rightarrow a=b \pmod c\ \land a=b \pmod d$ when $\gcd(c,d)=1$ Therefore I got two equations : $x^2 = x \pmod 8$ $x^2 ...
0
votes
1answer
22 views

LCM confusion question

A section of soldiers are rehearsing for the march past for the National Day parade . If they march in pairs , one soldier will be without a partner . If they match in threes , fives or sevens , they ...
0
votes
1answer
11 views

Numbers and percentage

When x is decreased by 15% and then increased by 20%, it becomes y. How to find this value of y? Express x:y in its simplest form The first step I done was to take away 15% from X which becomes 85% ...
0
votes
0answers
15 views

Find all $n$ so that the weights can be split into two groups

There is a set of $ n$ coins with distinct integer weights $ w_1, w_2, \ldots , w_n$. It is known that if any coin with weight $ w_k$, where $ 1 \leq k \leq n$, is removed from the set, the ...
0
votes
2answers
22 views

How to convert $12x =3 \pmod {93}$ to a form that can be used with the Euclidean algorithm?

I know that if I have to solve, for example, ${17x}\pmod {83} = 1$, I can convert that equation to $17x + 83y = 1$, and this latter equation can be used with the Euclidean algorithm. How should I ...
0
votes
1answer
27 views

Explain the order of elements in $\mathbb Z_{12}$

I cannot understand the cardinality of elements in modular classes like here explained, source of the latter is C1080. Definitions $\mathbb Z_{12}=\{\overline 0,\overline 1,\ldots, ...
0
votes
1answer
31 views

finding lowest number which solves modulo arithmetic equation

I'm having a some trouble trying to find the best solution. Given $i,b,m \in \mathbb N$ how do I find the smallest nonnegative integer $n$ that satisfies the equation $$i + bn \equiv 0 \mod m$$ Any ...
1
vote
1answer
38 views

How to find a number of integral solutions (all $x$)

If $A$ is between $[1..9000]$ $$A*X = 1 \pmod{9000}$$ All parameters are integers. I have found some solutions: $$A = 6907, X = 43,$$ $$A = 7111, X = 991$$ But I don't know how to find all $x$. I ...
2
votes
1answer
20 views

How to deal with an additive constant in a linear congruence equation?

I am trying to solve the following equation: $10x+3 \equiv 2 \pmod{17}$. The problem I am having is that I don't know what to do with the number $3$. This is what I have done so far: $10x+3 = ...
1
vote
3answers
63 views

Sum of possible all possible $x$ such that $51 \equiv 3 \pmod{x}$

I was asked this simple following question: What is the sum of all positive integers $x$ such that : $$51\equiv 3 \pmod{x}$$ My answer is $118$ (and I am pretty sure it's right but would like ...
2
votes
2answers
35 views

Perfect square is $0$ or $1$ modulo $4$ . [closed]

Prove that for every integer $n$ either $n^2 \equiv 0\pmod{4}$ or $n^2\equiv 1\pmod{4}$
0
votes
1answer
35 views

What is the largest prime number in the denominator of a fraction that creates a decimal that repeats every 4 digits?

I was studying a Target question for Math League competitions, and after a few hours of pondering, I finally came up with the following method of solving the mentioned problem: For any decimal, it is ...
0
votes
1answer
28 views

Calculate the quadratic residues in Z∗17.

Hello I am wondering if any one can help me I am trying to figure out how these below answers where came to too. Calculate the quadratic residues in Z∗17. Solution: This can be done by direct ...
1
vote
3answers
77 views

Evaluate the least significant decimal digit $ 109873^{7951}$

I am trying to understand the below, I can t seem to see or understand, how and why and where the answers where arrived at. Evaluate the least significant decimal digit of $ 109873^{7951}$ Solution: ...
0
votes
2answers
72 views

Evaluate all the square roots of 4 mod 77. [closed]

I have an exam coming up an this will be one style of question can anyone please walk me through how it is done? Sorry I am just totally confused and do not how to start Evaluate all the square roots ...
0
votes
1answer
20 views

Is $x^{n+1} \mod (m) = (x(x^n \mod (m))) \mod (m)$?

In my compsci studies I came along an alogorithm that makes perfect sense if this is true. However, I am unable to prove it, nor am I even able to find a proof or statement saying that it is true.
1
vote
2answers
31 views

Is the answer of $\ \ 2415^n \ mod \ \ 2556 \ \ $ is only $711$ and $1989$ for $n\in \mathbb{Z}^{+} >1 \ \ ?$

Is the answer of $\ \ 2415^n \ mod \ \ 2556 \ \ $ is only $711$ and $1989$ for $n\in \mathbb{Z}^{+} >1 \ \ ?$ If it's true, how to prove that ? I try to expand $(2556 - 141)^n $ for any ...
0
votes
0answers
32 views

Modulus-amplifying polynomials

I'm trying to prove that the family of polynomials $\lbrace P_k \rbrace$ defined as follows \begin{equation*} P_k(x) = (-1)^{k+1}(x-1)^{k} \left( \sum_{j = 0}^{k-1} \binom{k+j-1}{j} x^j \right) + 1. ...
1
vote
1answer
23 views

Group homomorphism preserves identity in modular arithmetic?

Suppose the set of residues $A=\{\bar 1, \bar 3, \bar 4, \bar 5, \bar 9\}$, $f(x,y)=x*y$, $\mathbb Z_{11}$ so the group is $G=\{A, f\}$ in $\mathbb Z_{11}$. The identity is $\bar 1$ as demonstrated by ...
0
votes
0answers
21 views

Extended Euclidean Algorithm (the going backwards step) and modular inverses

I have two questions. When computing the modular inverse of a number (computing $x^{-1} \bmod m$), in practice do people actually do "Mentally, what multiple of $x$, taken mod $m$, has a remainder ...
1
vote
1answer
16 views

Modulus Operation on powers of a number by hand

It is fairly straightforward to perform a modulus operation on small numbers by hand, but is there an easy way to find the modulus of larger numbers based on the smaller roots? For example: 180 mod ...
2
votes
3answers
40 views

Bezout's Identity proof and the Extended Euclidean Algorithm

I am trying to learn the logic behind the Extended Euclidean Algorithm and I am having a really difficult time understanding all the online tutorials and videos out there. To make it clear, though, I ...
1
vote
0answers
44 views

If $a^n+n^b\mid c^n+n^d$ for every $n$ then $c=a^k$ and $d=kb$ .

I made a generalization of the following problem (it's a problem from the IMO shortlist in some year) : Let $a,b$ be fixed positive integers . If : $$a^n+n \mid b^n+n$$ for every positive integer ...
1
vote
0answers
28 views

Modulus of large numbers

I am learning for an exam and want to understand this: Calculate $3^{142} \mod 50$. Solution: $\operatorname{HCF}(3, 50) = 1$ $\varphi(50) = \varphi(5 \cdot 5 \cdot 2) = \varphi(5^2 \cdot 2) = ...
3
votes
2answers
40 views

Integer solution of $ y-x = \sqrt{y+x} $

I have a problem with how to find integer solution of $\ \ \ y-x = \sqrt{y+x} \ \ \ which \ \ \ \ y>x$ $ y^2 -2xy + x^2 -y -x = 0 $ $ y^2 - (2x+1)y + (x^2 - x) = 0 $ $ y = \frac{(2x+1) \pm ...
0
votes
0answers
38 views

If $k \equiv ab \pmod n$ then $k^{-1} \equiv a^{-1} b^{-1} \pmod n$

How can I prove that if: $k \equiv ab \pmod n$ then $k^{-1} \equiv a^{-1} b^{-1} \pmod n$ ? Here is my attempt: Start from this congruence: $K K^{-1} \equiv 1 \pmod N$ Then try to reach this ...
0
votes
1answer
20 views

Can the remainder $r_2$ in the following be larger than $\frac{r_0}{2}$?

Let $n$ and $r_0 < n$ be integers. We define: $r_1 = n$ mod $r_0$ $r_2 = n$ mod $r_1$ Where we restrict $0 < r_1 < r_0$ and $0 < r_2 < r_1$. Is it possible for $r_2$ to be larger ...
1
vote
1answer
27 views

How to calculate $(a \cdot b\cdot c \cdot \ldots) \pmod{x}$

I need to calculate a basic equation $a \div b \pmod{c}$ where $a = x_1\cdot x_2 \cdot x_3 \cdot \ldots$ and similarly with $b$ where $c=10^9 + 7$. So I was wondering if it can be split up: $$a = ...