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
1answer
22 views

Show that the image or the kernel are submodule of R-module.

Let $R$ be Commutative ring and $M$ be an $R$-module. Show that $im(H)$ or $ker(H)$ are submodule of $R$-module $M$, where $$H\in Hom(M,-)$$ First, I think by lemma: If $M$ is an $R$-module and $N$ is ...
1
vote
8answers
73 views

Calculate the last digit of $3^{347}$

I think i know how to solve it but is that the best way? Is there a better way (using number theory). What i do is: knowing that 1st power last digit: 3 2nd power last digit: 9 3rd power last digit: ...
0
votes
0answers
26 views

Congruence equation $a^x \equiv 1$ mod $b$

Let $a, b, x$ be given numbers, then how to solve $a^x \equiv 1 \mod b$ ? ($1-a^x$)-integer part[$1-a^x /n]=0$ is the same?
0
votes
1answer
26 views

Solving a system of modular equatios

Edit: I can't actually see how Chinese remainder theorem works here, if we had only $x$ on the left of each equation I can see how I could work it, but we don't. I can't seem to reduce it down to just ...
3
votes
3answers
49 views

Is $(-1)^{1/8} + (-1)^{7/8}$ ever a value whose real component is $0$?

Is $$(-1)^{1/8} + (-1)^{7/8}$$ ever a value whose real component is $0$? Is this ever true in modular arithmetic, hypercomplexes, and/or both?
4
votes
2answers
543 views

Proof about prime numbers

Can we prove that every prime larger than 3 gives a remainder of 1 or 5(edited) if divided by 6 and if so, which formulas can be used while proving?
1
vote
2answers
35 views

Problem about proving fermat's little theorem

We know that, there is an important step to prove Fermat's little theorem, two side times $(n- 1)! \cdot a^{n-1} = (a\cdot1)\cdot(a\cdot2)\cdot...\cdot(a\cdot(n-1)) \equiv (n-1)! \mod(n) $ Example: ...
3
votes
3answers
28 views

If $n > 2$, prove that the order of the multiplicative group of units modulo n, $U_n$, is even.

I'm struggling with this. I know it is going to use Lagrange's Theorem so this is what I have so far: Suppose $|U_n| = k$ This implies $a^k = 1$ for all a in $U_n$ and $|a|$ divides $k$. Now, what ...
1
vote
1answer
41 views

Integer solutions of the equation $a^{n+1}-(a+1)^n = 2001 $

I am doing number theory and I came across that question $a^{n+1}-(a+1)^n = 2001 $. Find the integer solutions and show that they are the only solution. I really tried hard but i am nowhere near ...
4
votes
0answers
24 views

Subsets of cyclic group with distinct pairwise differences

Given a number $m\in\mathbb N$, let $\mathbb Z_m=\{0,1,\dots,m-1\}$ denote the ring of integers modulo $m$ (although we won't need multiplication, so any cyclic group of order $m$ will do). Given a ...
1
vote
1answer
28 views

Proof on Divisibility of Binomial Coefficients

Prove that $\exists \ i$ $(0 \lt i \lt n)$ such that $$ n \nmid {n \choose i} $$ $\forall \ n$ such that $n \gt 0$ and $n$ is a composite Number.
0
votes
2answers
16 views

If $c \not\equiv 0 \pmod p$ then $\forall a \not\equiv 0\ \exists b \not\equiv 1$ so $c+a\equiv ab \pmod p$

Im looking for a correct argumentation of why the folowing holds, any help would be great: For $p$ prime, if $c \not\equiv 0 \pmod p$ then $\forall a \not\equiv 0 \pmod p ~\exists b \not\equiv 1 ...
4
votes
4answers
80 views

Prove that $a^7-a$ is divisible by 168 when a is odd

so I saw a similar question that proves $168\mid(a^6-1)$ when $(42,a) = 1$. But for this problem I was not given that gcd$(a,42)=1$. When I factor out a I get $168\mid a\cdot(a^6 - 1)$ and since $a$ ...
2
votes
3answers
65 views

Find the remainder of $40^{314}$ divided by 91.

Here's what I have so far. $$x \equiv 40^{314} \mod{91}$$ $$\Rightarrow$$ $$x \equiv 40^{314} \mod{7}$$ $$ x \equiv 40^{314} \mod{13}$$ Then by FLT, $$40^6 ≡ 1 \mod{7}$$ $$40^{12} ≡ 1 \mod{13}$$ ...
3
votes
3answers
56 views

How to prove that $a+b$ is a multiple of $24$?

Let $x$ be an integer one less than a multiple of $24$. Prove that if $a$ and $b$ are positive integers such that $ab=x$, then $a+b$ is a multiple of $24$.
0
votes
1answer
19 views

Let $m=p^t$ where p is a prime. Prove that $a^{\phi(m)+t} \equiv a^t \bmod{m}$ for ${\bf all}$ integers a

So, I was thinking that $a^{\phi(m)}\equiv 1 \bmod{m}$, thus when multiplying $a^t$ on both sides, we get that $a^{\phi(m)+t} \equiv a^t \bmod{m}$. What is throwing me off is the all integers a part.
3
votes
4answers
26 views

Least positive residue of $10! mod 143$

So I got that $10! \equiv 10\ (\textrm{mod}\ 11)$ and $10! \equiv 9\ (\textrm{mod}\ 13)$ but I am not sure how to apply the chinese remainder theorem to arrive at the solution for $x \equiv 10!\ ...
0
votes
2answers
33 views

Modulo arithmetic a = 1 mod n

If I know value of $a$ and also it is known that $$a \equiv 1 \pmod n$$ how can I calculate value of $n$?
0
votes
1answer
26 views

How to apply modular arithmatic in expression containing divisions?

How do I find the modulo if the expression contains divisions. Like: $$\frac{p^a-1}{p-1} \pmod{1000,000,007},$$ where $(p^a-1)$ is divisible by $p-1$ and p is a prime, but a may not be. How do I ...
1
vote
1answer
18 views

(Counting problem) very interesting Modular N algebraic eqs - for combinatorics experts

We have some attempt to numerically solve this math problem, which means that we like to count the number of independent solutions of this set of six of modular N algebraic equations: $$ (1) x_1 ...
0
votes
2answers
197 views

find a general expression for the remainder when a prime divides a fibonacci.

I have primes of form $5k\pm1$. Consider the equation: $F_n=f(n)\pmod p$ where $F_n$ is the nth fibonacci number. Now given a c, how can i check whether or not there exists a solution for $f(n)=c ...
1
vote
1answer
62 views

How to count soldiers in the army using Chinese Remainder Theorem?

You are a chinese general and you want to count your army. Your estimate is 790,000 - 810,000. Propose the counting to determine the result unambiguously. The soldiers can only count from to 1 to 12. ...
1
vote
4answers
48 views

Problem modulo $p$.

Let $p$ be a odd prime, prove that $1^p+2^p+...+(p-1)^p \equiv 0 \mod p$ I'm not sure how to do this, thanks.
0
votes
1answer
19 views

Addition on an Elliptic Curve and Modular Arithmetic involving fractions

I'm having a bit of an issue with addition on elliptic curves. For example, I've been given the curve $Y^2 = X^3 + 2X + 1$, working modulo 3. Now, say I want to add the point $(1,2)$ with itself. To ...
1
vote
1answer
34 views

If $\sigma(p^m)=2^n$ for prime $p$,then $m=1$ and $n$ is prime

Exercise from Beginning Number Theory by Neville Robbins: Let $\sigma(a)$ denote the sum of divisors of $a$.Then we have to prove that if $\sigma(p^m)=2^n$ for some prime $p$,then $m=1$ and $n$ is ...
2
votes
2answers
27 views

Find all solutions to this system of congruences

$$x \equiv 11 \pmod{84} $$ $$ x \equiv 23 \pmod{36}$$ I have the bulk of the work done for this; $x=11+84j$ $x=23+36k$ $\Rightarrow 11+84j \equiv 23 \pmod{36}$ $\Rightarrow 84j \equiv 12 \pmod{36}$ ...
1
vote
2answers
40 views

Find an integer $x$ satisfying the congruence:

$$x \equiv \ 1 \pmod3$$ $$x \equiv \ 2 \pmod5$$ $$x \equiv \ 8 \pmod{11}$$ From the first, I have $x=3k+1$, $x=5j+2$ from the second and $x=11l+8$ from the third. Subbing the third into the second I ...
2
votes
2answers
47 views

Describe all integers a for which the following system of congruences (with one unknown x) has integer solutions:

$$x\equiv a \pmod {100}$$ $$x\equiv a^2 \pmod {35}$$ $$x\equiv 3a-2 \pmod {49}$$ I'm trying to solve this system of congruences, but I'm only familiar with a method for solving when the mods are ...
2
votes
1answer
35 views

Problem on Number of Quadratic Residues

We have two primes $p,q$ and an integer $a$ such that $$\gcd(a,pq)=1$$ How to prove that for the following congruence $$x^2 \equiv a \mod pq$$ either there will be $4$ solutions or $zero$ solutions. ...
0
votes
4answers
31 views

Computing elliptic curve finite field modular arithmetic

Sorry for asking such a n00b question but what does the following compute to? $s=(3(16)^2+9)\cdot(2\cdot 5)^{-1}\bmod{23} = 11$ In an online response here, I saw this computes to $11$ but whenever I ...
0
votes
2answers
35 views
-1
votes
2answers
30 views

How to prove this modular problem?

Prove that if $n^2+m$ and $n^2-m$ are perfect squares, them $m$ is divisible by $24.$ How to solving this problem?
0
votes
2answers
16 views

Extended Euclidean Algorithm for Modular Inverse

I'm currently learning how to find the inverse of a modulo with the Extended Euclid Algorithm and I stumbled upon a problem when finding an inverse when the $m>p$ as for $m \equiv 1 \pmod{p}$ For ...
0
votes
2answers
32 views

How to prove that gcd(k! mod m, m) > 1, for every k > $\alpha$

I'm doing some exercises and I've read that, if $\alpha$ is the first prime factor of a number $m \geq 2$, then, for every $k \geq \alpha$, it is true that $gcd(k!\ mod\ m,\ m) > 1$. I can see ...
1
vote
4answers
28 views

Are $a$ and $n$ relatively prime?

Suppose that $a$ and $n$ are integers, $n>1$. Prove that the equation $ax\equiv1(\mod n)$ has a solution if and only if $a$ and $n$ are relatively prime. How to solving this problem?
0
votes
0answers
24 views

Computing square root modulo prime square

My problem is to find $x$ when $x^2\equiv n \space mod \space p^2$ for some given $n$ and $p$. I can use Tonelli-Shanks algorithm to find the solution $mod\space p$, but it doesn't work for $p^2$. ...
0
votes
0answers
15 views

Question regarding a surjective function

The function $f :\mathbb{Z}_{12} \longrightarrow \mathbb{Z}_4$ is defined by $f(x)=3x$. I am asked given any $a,b \in \mathbb{Z}_{12}$ if preservation of addition and multiplication occur. I proved ...
0
votes
5answers
49 views

Prove that $p^q+q^p\equiv p+q \mod pq$

I can prove $p^{q-1}+q^{p-1}$ is congruent to 1 mod $pq$ very easily, but with the $p+q$ it doesn't fit a theorem I can find. The only ones I find say if they are congruent to $b$. I get one is ...
0
votes
1answer
40 views

Is there this integers [duplicate]

Given an integer n, show that an integer can always be found which contains only the digits 0 and 1 (in the base 10 notation) and which is divisible by n. How to solving this problem?
2
votes
5answers
134 views

Prove they cannot both be integers

Prove that $\frac{21n-3}{4}$ and $\frac{15n+2}{4}$ cannot both be integers for the same positive integer $n$. How to solving this problem?
1
vote
1answer
30 views

Prove that there exists an integer n

Let a,b,c,d be fixed integers with d not divisible by $5$. Assume that m is an integer for which $am^3+bm^2+cm+d$ is divisible by $5$. Prove that there exists an integer $n$ for which ...
5
votes
6answers
178 views

Show that if n divides a single Fibonacci number., then it will divide infinitely many Fibonacci numbers. [duplicate]

Show that if n divides a single Fibonacci number, then it will divide infinitely many Fibonacci numbers.
0
votes
2answers
17 views

How does one compute how big the cycle of modding by a prime number is?

If I take the $k \in \mathbb{N}$ power of 10 and mod it by a large prime, I notice that the remainders repeat at some point. For instance $10^k mod~7$ seems to repeat every $8$th value of $k$. Given ...
0
votes
1answer
44 views

Remainder of $1946^{1972} : 26$

Is this correct? $1946^1 = 22 \mod{26}$ $1946^2 = 22^2 = 484 = 16\mod{26}$ $1946^3 = 22^2 * 22 = 16 * 22 = 14 \mod{26}$ $1946^4 = 22^2 * 22^2 = 16^2 = 22 \mod{26}$ And therefore for any integer ...
0
votes
1answer
5 views

Calculate power of large numbers mathematically?

Is there a short-hand method to find the value of a number with a large power. For example : 1024^2048
0
votes
1answer
11 views

How to decide whether a number is inside of wrapped (modular) interval

I am having a problem a finding a suitable formula for deciding whether a number falls inside of modular interval. Example: Let's use $mod$ $100$ and the interval $\langle 90, 10\rangle$. How would ...
1
vote
4answers
40 views

How to find $k$ in $6^{k} \equiv 2 \mod {13}$

Find for which $k$ is $6^{k} \equiv 2 \mod {13}$ I'm having trouble with these types of question in my cryptography class. This is part of Diffie–Hellman algorithm for calculating a shared key. ...
1
vote
2answers
50 views

Determine the last two digits of $3^{3^{100}}$

Determine the last two digits of $3^{3^{100}}$ This is one of the problems in the past exam my modern algebra course. I think I need to use euler-fermat theorem but can't figure out how to use it for ...
0
votes
2answers
23 views

Congruence and GCD relation proof

I came across this theorem: For all integers a,b,c and m>0, if d = GCD(c,m) then ...
0
votes
0answers
10 views

Preservation of a map

There is a map from Z(mod12) to Z(mod4) defined by f(x)=3x. The thought I had was this. Say you have [a],[b] that are in Z(mod12). Would f([a][b])=f([a])f([b])? So you basically view this as a ...