1
vote
5answers
79 views

finding mod of an expression with variables

I've been asked to show that: $n(n+1)(2n+1) \equiv 0 (\bmod 6)$ I found in a previous question that: $n(n+1)$ was divisible by $2$ and resulted in an even number e.g $n(n+1) \equiv 0 (\mod 2)$ so ...
0
votes
1answer
25 views

Converting infinite base-k expansions into base-j expansions

I understood the method of transforming a finite sized base-k numbers to another base (j) through the use of successive divisions For example $$12_{10} = 12/2 + 0*2^0 = 6/2 + 0*2^1 + 0*2^0 = 3/2 + ...
0
votes
0answers
39 views

What is the remainder of this big number without doing major calculations?

I am solving a problem and came across a situation where to calculate remainder for big values with out doing major calculation. In my case I need to compute the expression: $$2^{n}-1+k ...
2
votes
3answers
51 views

What is remainder when $5^6 - 3^6$ is divided by $2^3$ (method)

I want to know the method through which I can determine the answers of questions like above mentioned one. PS : The numbers are just for example. There may be the same question for BIG numbers. ...
0
votes
3answers
57 views

Prove that $n^2 + 1$ is not a multiple of $6$ for any positive integer $n$

Prove that $n^2+1$ is not a multiple of $6$ for any positive integer $n$. I i think prime factorization would be a good way to go about this problem but I need some help.
7
votes
1answer
105 views

An analogue of Hensel's lifting for Fibonacci numbers

In this question Oleg567 conjectured the following interesting fact about Fibonacci numbers: $$ k\mid F_n\quad\Longrightarrow\quad k^d\mid F_{k^{d-1}n} $$ that can be regarder as an analogue of the ...
1
vote
2answers
41 views

Show that if $a^h ≡ 1\mod p$ then $ a^{ph} ≡ 1 \ \mod p^2$.

I don't know how to proceed. I know that regardless of what h is, it divides the order of a modulo $p$. I also know that the order of a divides $\phi(p) \ \text{mod} \ p$, where $\phi$ is Euler's ...
0
votes
3answers
39 views

x≡1 (mod 8) x≡9 (mod 12) has solution x = x_0. How many solutions mod 24 are there to the system of congruences?

Say, x≡1 (mod 8) x≡9 (mod 12) has solution x = x_0. How many solutions mod 24 are there to the system of congruences? I am worried this question is too easy to be true. That is why I am confused. ...
0
votes
1answer
42 views

Congruence and percentage

Suppose I have three statements of congruence: x = a mod n, y = b mod m, z = c mod p; Furthermore, x is a given percent of x + y + z, as is y and z. Does this uniquely determine x, y, z? Or does it ...
6
votes
1answer
59 views

Matrix restoring (modulo n)

Let $m,n\geqslant 2$, and $A\in \mathcal{M}_n(\mathbb Z)$ such that $\det A \equiv 1 \pmod m$. Does it (necessarily) exist $M\in \mathrm{GL}_n(\mathbb Z)$ such that $A\equiv M \pmod m$?
0
votes
1answer
185 views

Why elements of the set can be Goldbach pairs for a given even number?

Let's take even number $100$ as an example (an example in the paper): Fom $2$ to $\sqrt{100}$ there's four primes:$\ 2,\ 3,\ 5,\ 7.\ $Let $$ \begin{align*} &A=\{n: n \in \mathbb{Z^+}, ...
1
vote
4answers
56 views

Is it possible to do modulo of a fraction

I am trying to figure out how to take the modulo of a fraction. For example: 1/2 mod 3. When I type it in google calculator I get 1/2. Can anyone explain to me how to do the calculation?
1
vote
1answer
49 views

PowerMod: Solving for the base

Given the problem $c^d \mod n = m$ and values for $d$, $n$, and $m$, how would one solve for $c$? A general solution or approach would be fine, as well as the values for my specific problem are as ...
1
vote
1answer
48 views

Solving Equations in $\mathbf{Z}/n\mathbf{Z}$ with Indices

Consider the equation $x^4 = 7,$ which we wish to solve in $\mathbf{Z}/29\mathbf{Z}.$ I was taught a technique for solving this problem, but I can't understand it. I'll try my best to describe it, ...
0
votes
2answers
33 views

calculate reverse number with 2 conditions

I can't find the reversed number of $2 \mod 13$ ($2^{-1}=?$) that is also a solution to $$5x = 2 \mod 13.$$ How can I find it? Thanks!
3
votes
1answer
41 views

Number theory notation

I am confused with the below notations . I know that ($a \equiv b \mod {n} )\iff ( n|(a-b)$ ) but what the below notation says ? $a = b \mod {n}$ and in theorem 16 in this ,it's given as below ...
3
votes
2answers
152 views

Number theory problem.Primes modules.

If $$a^p\equiv b^p \pmod p$$ where $p$ is prime prove that $$a^p\equiv b^p \pmod{p^2}$$ that problem was at my exam today on number theory and i just didnt have a clear mind to solve it.Although i ...
2
votes
2answers
41 views

Correct reasoning when proving the multiplication property in modular arithmetic?

I am trying to understand why this rule works: \begin{align*} a \equiv b \pmod c \quad k \equiv j \pmod c \qquad &\implies \qquad ka\equiv jb \pmod c \end{align*} I saw that the proof is ...
0
votes
1answer
41 views

Polynomial Diophantine Equations

So in general how does one decide if: $$ a_0 + a_1x + a_2x^2 ... a_{n_1}x^{n_1} = b_1y + b_2y^2 ... + b_{n_2}y^{n_k}$$ Has solutions for integers $x,y$ given real numbers $a_0, a_1. .. a_{n_1}, b_1 , ...
0
votes
1answer
45 views

To prove that ${2+i \choose i}\equiv k \mod n$ is not possible that $k=0,1,\ldots,n-1 \forall i\ge 0$ and $i \in \mathbb{Z}$ and $n$ is odd.

To prove that ${2+i \choose i}\equiv k \mod n$ is not possible that $k=0,1,\ldots,n-1 \forall i\ge 0$ and $i \in \mathbb{Z}$ and $n$ is odd. This is a problem from ISI 2014 written test in a little ...
2
votes
3answers
98 views

How do you prove that $ n^5$ is congruent to $ n$ mod 10? [duplicate]

How do you prove that $n^5 \equiv n\pmod {10}$ Hint given was- Fermat little theorem. Kindly help me out. This is applicable to all positive integers $n$
2
votes
1answer
45 views

The existence of primitive algebraic units modulo 3

Consider the problem of computing $$\sqrt{2} \mod 3 $$ Whereas we seek a number $n$ such that $n^2 \equiv 2 \mod 3$ and furthermore it is known that both $n$ and $2n$ will satisfy this property, ...
1
vote
5answers
98 views

If $a, b$ are relatively prime proof.

Prove that if $a$ and $b$ are relatively prime integers and $ab$ is a perfect square so are $a$ and $b$. Show by counterexample that the relatively prime condition is necessary. I dont know how ...
-3
votes
2answers
35 views

Proofs for modular arithmetic

$\rm(a)$ Prove that for any pair $a,b$ of positive integers there are integers $x,y\in\Bbb Z$ such that $ax+by=\gcd(a,b).\ $ (Hint: Use the well-ordering principle on the set of integer linear ...
2
votes
0answers
29 views

Given any integers $a,b,c$ and any prime $p$ not a divisor of $ab$, prove that $ax^2+by^2\equiv c\pmod{p}$ is always solvable.

The fact that there are $\dfrac{p+1}{2}$ quadratic residues seem to me to help solving the question, but I don't know how to go on from that point. Could you give me any hint?
1
vote
1answer
33 views

Divisibility of sum of exponents

Consider the sequence $$r, \ ra, \ ra^2, \ ra^3, ... \ , ra^n \mod M $$ such that: $$ ra^{n+1} \equiv r \mod M$$ and $a \ne 1$ and $a,r$ are both coprime to $M$ Is it always true then that: ...
2
votes
2answers
103 views

Prove that $a^n+b^n \equiv (a+b)^n \mod n$, if $n$ is prime and $a,b$ are integers.

What is the best method to prove that if $n$ is prime and $a,b$ are integers $a^n+b^n \equiv (a+b)^n \mod n$, ?
0
votes
1answer
34 views

Solution for generalized Euler's Theorem $a^m\equiv a^{m-\phi(m)} \pmod{m}$?

The above identity holds for any integer $a$. Since my solution(?) does seem neither elegant nor rigorous enough, I want to get some advice to improve it. My solution: If $(a,m)=1$, this identity is ...
0
votes
1answer
55 views

How do I find the inverse of $e \bmod (p-1)(q-1)$?

I'm trying to find this inverse modulo to set up a solution for an RSA cipher. I haven't the slightest how to go about this. When I looked up the formula for such a question, it states: $$ d \equiv ...
0
votes
0answers
25 views

Divisibility Method

Is there exist any known method to find divisibility rule of each and every rational number in any numeral system by analysing its reciprocal. And additionally it will give the remainder on division ...
-1
votes
1answer
35 views

$p>3$ prime, show that there exists $0<x,y<\sqrt{p}$ so that $p$ divides $cx-y$

Let $p>3$ be a prime number that does not divide $c$. Show that if $p>3$ there exists $x$ and $y$ with $0<x,y<\sqrt{p}$, such that p divides $cx-y$. I believe I've shown the above but for ...
0
votes
1answer
80 views

What is the remainder when $24^{1202}$ is divided by $1446$?

I tried remainder theorem but that does not simplify it. I tried factorizing $1446$ as $2\cdot3\cdot241$ and got remainders when numerator is divided by $2,3$ and $241$ individually but then I did ...
2
votes
4answers
253 views

Find number x such that $x\equiv 4^{1002}\pmod{55}$

Find a natural number x, for $0 \le x \le 54$ such that is a solution for the following equation: $$x\equiv 4^{1002}\pmod{55}$$ This question was asked in an exam, so I expect that the answer is ...
2
votes
2answers
47 views

Showing equality of primitive roots with quadratic non-residues.

Suppose that $p$ and $q = 2p + 1$ are both odd primes. Show that the $p − 1$ primitive roots of $q$ are precisely the quadratic non-residues of $q$, other than the quadratic non-residue $2p$ of ...
0
votes
0answers
34 views

Sum of the jumbled digits of $abc_{10}$ is $3194$

In the book that I am reading, the author denotes $abc_{10}$ as $100a+10b+c$ where $a, b, c \lt 10$. So if $a = 3$, $b=2$ and $c=8$ then $abc_{10} = 328$. The author asks the following problem: In ...
0
votes
1answer
32 views

How to show $2^{k+2}$ divides $3^{2^k}-1$ but $2^{k+3}$ doesn't?

I've got a task: Find highest power of 2 that divides $3^{2^k}-1$ so i wrote few terms and guessed that it's $2^{k+2}$, now i should show it. I tried by induction, but what i got appeals to me as a ...
0
votes
1answer
24 views

Find all values of parameter A such that two system of congruences are equal

I'm starting to learn some elementary number theory and i came across a task i don't know how to solve. $$x \equiv 5 (mod \ 6)$$ $$x \equiv A (mod \ 35)$$ and the second one $$x \equiv A (mod \ ...
1
vote
0answers
31 views

solving congruence equation system modulo prime

I need to solve a congruence system like this: $30f_0+26f_1+8f_2+38f_3+2f_4+40f_5+20f_6 \equiv 0 \pmod{41}$ $38f_0+2f_1+40f_2+20f_3+30f_4+26f_5+8f_6 \equiv 0 \pmod{41}$ ...
1
vote
4answers
53 views

Find the smallest integer $n\geq1$ such that $35n$ is a perfect square and $n/7$ is a pefect cube.

Find the smallest integer $n\geq1$ such that $35n$ is a perfect square and $n/7$ is a pefect cube. What I have so far: we express the prime factorizations of $35$ and $7$ as $5\cdot7$ and $7$, ...
2
votes
0answers
21 views

System of equations - modular arithmetic

I am asked to solve the following..... Let $n\in \mathbb{N}$ and suppose that $a,b,c,d,k,l\in\mathbb{Z}$. Consider the system $ax + by \equiv k$ mod $n$ and $cx+dy \equiv l$ mod $n$. Let $D=ad-bc$. ...
0
votes
2answers
73 views

Count subsets whose cardinalities are congruent to 0, 1 and 2 modulo 3 respectively

Given a set of N elements, compute the number of subsets whose cardinalities are congruent to 0, 1 and 2 modulo 3 respectively. Any hints would be appreciated. Thanks!
1
vote
1answer
30 views

Solution set to exponential in congruence

For which $n>0$ does $x^{2^n} \equiv 7 (mod \ 9)$ have a solution? It might be useful to start $x^{2^n} \equiv 16 (mod \ 9)$ but how should one proceed? Any hints would be appreciated. Thanks!
0
votes
1answer
27 views

A form of Chinese remainder theorem

How can we solve equations of the form $c \equiv a \mod b$ for finding the c? Also, sometimes $c$ can be two different numbers, one negative and one positive, when is that possible and how does it ...
-2
votes
2answers
51 views

Find the natural numbers $n$ in which $n^2$ divides $584$? [duplicate]

I'm trying to find the natural numbers $n$ in which $n^2$ divides $584$ ? i tried all the ways i know but i get stuck.
6
votes
2answers
257 views

Sum of Digits Question

If A is the sum of the digits of $5^{10000}$, B is the sum of the digits of A, and C is the sum of the digits of B, what is C? I know it has something to do with mod 9, but I'm not sure how do use it ...
1
vote
1answer
35 views

Primitive roots used to work out $x^7 \equiv 5 \pmod {11}$

I have a workbook question that doesn't have any example solution, that is as follows: Primitive roots used to work out $x^7 \equiv 5 \pmod {11}$ Now I can see $\phi(11)=10$ and $2$ has order $10$ ...
2
votes
2answers
50 views

Show that an integer of the form $8k + 7$ cannot be written as the sum of three squares.

I have figured out a (long, and tedious) way to do it. But I was wondering if there is some sort of direct correlation or another path that I completely missed. My attempt at the program was as ...
1
vote
3answers
83 views

Verify that $4(29!)+5!$ is divisible by $31$.

Verify that $4(29!)+5!$ is divisible by $31$ I know I have to use Wilsons theorem: $(p-1)!=-1\pmod p$ but I'm not really sure how to apply this theorem. Step by step explanation please? Thank you!
1
vote
3answers
40 views

Modulo Inverse using extended euclidean

My aim here to learn the Chinese Remainder theorem. But am stuck at finding the inverses. Suppose we have 42 mod 5, but according to the CRT question, we must make it 42 * x congruent to 1 (mod 5) ...
0
votes
1answer
32 views

what are the values of m when $m(3^{2m}+3) \equiv 0 \mod 28$?

Can you help me with this problem. I want to know what are the values of m which makes $m(3^{2m}+3) \equiv 0 \mod 28$.