Questions on congruences, linear diophantine equations, greatest common divisor, divisibility, etc.

learn more… | top users | synonyms

4
votes
1answer
42 views

Modulo Arithmetic of Complex Numbers

Suppose $a,b,c \in \mathbb{C}$ such that $$a+b+c\in \mathbb{Z},$$ $$a^2+b^2+c^2=-3,$$ $$a^3+b^3+c^3=-46,$$ $$a^4+b^4+c^4=-123$$ then find $(a^{10}+b^{10}+c^{10})\pmod{1000}$. I only observed that ...
1
vote
1answer
25 views

Existence of a generator over multiplication for integers modulo p

If we consider the integers modulo a prime $p$, then for every $x \not \equiv 0$ (mod $p$), we can get any $b \not \equiv 0$ by adding $x$ a number of times to itself. Is the same true for ...
2
votes
3answers
59 views

Sum of squares and $5\cdot2^n$

Does anyone know of a proof of the result that $5\cdot2^n$ where $n$ is a nonnegative integer is always the sum of two squares? That is, nonzero integers $x,y$ must always exist where: ...
0
votes
2answers
39 views

Properties of addition and multiplication modulo $m$

I was studying some number theory and I came across this theorem in a book, but unfortunately there was no proof of it. Can somebody tell me the proof? $$(a + b) \bmod m = ( (a \bmod m) + (b \bmod m) ...
1
vote
0answers
15 views

Bertrand's postulate for primes congruent to 1 modulo 4

One should be able to show that there is a prime congruent to 1 modulo 4 between n and 2n for every sufficiently large n. Does anyone know a reference for this with an explicit bound on how large n ...
0
votes
3answers
31 views

Chinese Remainder Theorem Finding the Modulo

Find numbers $t,u,v$ so that $33t+2 = 20u+13 = 29v-1 $ This is a Chinese Remainder Theory problem, but the problem I am having is finding what are the appropriate modulo. I figure it is easiest to ...
1
vote
2answers
71 views

Fermat's theorem, sum of prime squares.

By Fermat's theorem, a prime $p$, is a sum of two squares if and only if $p \equiv 1 \pmod 4$. I am wondering if there is any extension of this theorem or result that will give me the primes of the ...
0
votes
2answers
24 views

How to prove $x^2=-1$ has a solution in $\mathbb{Q}_p$ iff $p=1\mod 4$

Let $p$ be prime and let $\mathbb{Q}_p$ denote the field of $p$-adic numbers. Is there an elementary way to prove $x^2=-1$ has a solution in $\mathbb{Q}_p$ iff $p=1\mod 4$? I need this result, but I ...
2
votes
1answer
52 views

Group-like structures over the integers and functions on them

The integers with addition build a group $\langle \mathbb{Z},+,0\rangle$. The functions $\operatorname{succ}:\mathbb{Z} \rightarrow \mathbb{Z}$, $\operatorname{pred}:\mathbb{Z} \rightarrow ...
2
votes
1answer
44 views

Prove that $13 | (a^2 + b^3) \Rightarrow 13|b$

I have to prove that $13|(a^2+b^3)\Rightarrow 13|b$. I know that: $13|a \land 13|b \Rightarrow 13|(a+b), $ $13|a \Rightarrow 13| a^2,$ $13|b \Rightarrow 13| b^3,$ $13|a \land 13|b \Rightarrow ...
1
vote
4answers
48 views

Prove or disprove: there is an integer $x$ so that $x \equiv 2$ (mod 6) and $x \equiv 3$ (mod 9).

Prove or disprove: there is an integer $x$ so that $x \equiv 2$ (mod 6) and $x \equiv 3$ (mod 9). I'm not too sure how to approach this. I first noted that $(6,9) = 3 \neq 1$ so I cannot use ...
2
votes
3answers
30 views

Solutions for a system of congruence equations

I have a system $$ \begin{cases} x \equiv 7 \pmod{15} \\ x \equiv 14 \pmod{33} \end{cases} $$ How can I show that the system does not have any solutions? I know that the first implies that $x = ...
3
votes
7answers
140 views

For what $n$ is $n! = 2^8\cdot3^4\cdot5^2\cdot7$?

How can one find $n$ when $n! = 2^8\cdot3^4\cdot5^2\cdot7$? And generally, How to solve this kind of questions? The textbook provided a poor answer.
1
vote
1answer
219 views

There does not exist a perfect square with all decimal digits 0 or 6 [closed]

How to show that there is no perfect square whose decimal representation consists entirely of digits 6 and 0?
4
votes
1answer
56 views

Show that $\limsup \pi(n)/n = 0$ with elementary techniques.

Suppose $S$ is a set $S \subseteq N$ and suppose $$\lim_{n \to \infty} \frac{|Z_n \cap S|}{n} = c \in (0,1).$$ How do we prove, using elementary means, that there is a composite number in $S$? If ...
0
votes
0answers
30 views

Why is $x^2=a \pmod{p_1p_2}$ solvable when $x^2=a \pmod {p_i}$ is solvable?

Burton - Number theory If $x^2=196 \pmod {23}$ and $x^2=196 \pmod{59}$ are solvable, then $x^2=196 \pmod{23\cdot 59}$ is solvable. Why? Here, since $\gcd(196,23\cdot 59)=1$, ...
3
votes
1answer
51 views

How find prime numbers $p_{i}$ such $p_{1}+p_{2},p_{2}+p_{3},p_{3}+p_{4},\cdots,p_{n}+p_{1}$ is square number

Question: Let $n\ge 5$ be an odd number, show that: there exist (or does not exist) primes $p_{i}\:;\:i=1,2,\cdots,n$ such that $$p_{1}+p_{2},p_{2}+p_{3},p_{3}+p_{4},\cdots,p_{n}+p_{1}$$ all ...
0
votes
2answers
62 views

Prove that $x=0.1234567891011\cdots$ is irrational [duplicate]

Prove that $x=0.1234567891011\cdots$ is irrational Proof: we argue by contradiction.suppose x is rational. then its decimal expansion ultimatetly periodic. Lets p denote the perid of this expansion. ...
2
votes
0answers
30 views

divisibility and k-power sum

Let $a_{1},\dots,a_{n},\,n>2$ distinct natural numbers. Prove that if $p_{1},\dots,p_{r}$ are prime numbers and they divide $a_{1}+\dots+a_{n}$ then exists an integer $k>1$ and a prime $p\neq ...
2
votes
1answer
36 views

If $p,q$ are prime numbers prove that $p=q^2+q+1$.

Prove that if $p$ and $q$ are prime numbers such that $p|q^3-1$ and $q|p-1$ then: a) $p|(q^2+q+1)$ b) $p=q^2+q+1$ It is easy to prove part a but I am having troubles with part b. Does anyone have ...
10
votes
3answers
1k views

What is wrong with this proposed proof of the twin prime conjecture?

I was thinking on the twin prime conjecture, that there are an infinite number of twin primes... I came up with a proof. I have to think that it is incomplete or wrong, because many great minds ...
2
votes
1answer
85 views

Question on congruence

Prove if $n|m$ where $n$ and $m$ are integers greater than $1$ and $a ≡ b ($ mod $ m)$ then $a ≡ b($ mod $n)$
2
votes
0answers
35 views

prove two sets have the same g.c.d.

$a_n,b_n$ are two sequence valued in $[0,1]$ and $a_0=1,b_0=0 $. the following equation holds: $$a_n=\sum_{k=1}^{n}b_ka_{n-k}\tag{1}$$ $$A=\{n:a_n>0\}-\{0\}$$$$B=\{n:b_n>0\}$$ further ...
7
votes
4answers
119 views

Binary operation commutative, associative, and distributive over multiplication

Is there any binary operation that is commutative, associative, and distributive over multiplication? I asked this question in my head a while ago, and I posted it in various forums. However, having ...
2
votes
2answers
33 views

If $2a^2 = b^2$ then $2$ is a common divisor of $a$ and $b$?

The question is: Prove the statement or disprove it using a counterexample. If $2a^2 = b^2$, where $a,b\in \mathbb Z$, then $2$ is a common divisor of $a$ and $b$? The only thing that works ...
1
vote
2answers
44 views

Help with understanding this proof in discrete mathematics?

This is the question and solution: Q: Prove that for any integer $a$, $2a + 1$ and $4a^2$ + 1 are relatively prime. A: Since $4a^2 + 1 = (2a − 1)(2a + 1) + 2$, any common divisor of $2a + 1$ and ...
3
votes
1answer
34 views

Prove that $\gcd(6n-1, 2n-4) = 1$ or $11$

Question: Prove that if $n$ is an integer, then $\gcd(6n-1, 2n-4) = 1$ or $11$. Would I have to use the Euclidean algorithm to solve this problem? How would I go about finding values of $n$ ...
1
vote
1answer
45 views

Name of Legendre symbol?

This may seem stupid question, but I'm curious about this. Generally, $(a/p)$ is called "the Legendre symbol" where $p$ is an odd prime, but I don't like this naming since this naming is not formal. ...
1
vote
0answers
23 views

Proving Euler’s congruence and Legendre

So the question is "Prove Euler's congruence $a^{\frac{p-1}{2}} \equiv \left(\frac{a}{p}\right) \bmod p$ for odd primes p and a in $\\Z$." So I know that $$\left(\frac{a}{p}\right) = \begin{cases} ...
1
vote
1answer
21 views

Using Euler theorem show that $a^{\frac{\varphi(m)}{2}}\equiv \pm1 \pmod m,~where~(a,m)=1$.

Euler Theorem: $a^{\varphi(m)}\equiv 1 \pmod m ,$ For $(a,m)=1.$ Using the above show that for $m=p^\alpha$ where $p$ is prime and $m\geq3$ $$a^{\frac{\varphi(m)}{2}}\equiv \pm1 \pmod ...
1
vote
1answer
48 views

Fermat's $p=a^2+b^2$ theorem

There is one little part of the proof I didn't quite get. If we assume that $p$ is a prime such that $p \equiv 1\pmod 4$ and $x$ an element of order $2$ in $\mathbb{Z}_p$. Why $x$ must be equal ...
-1
votes
1answer
75 views

Prove that there are infinity many numbers you can't write in the form $a^{T(a)}+b^{T(b)}$.

Prove that there are infinity many numbers you can't write in the form $a^{T(a)}+b^{T(b)}$ where a and b are positive integers. T(a) represents the number of divisors number a has.
12
votes
2answers
148 views

How can I prove analytically the number $2^{100000}+1$ is not prime??

How can I prove analytically the number $$(2^{100000}+1)$$ is not prime??
0
votes
0answers
58 views

Can we use the distance to nearest prime to approximate large integers?

Let's say we have two oracles, NearestPrime and IndexOfPrime, defined as follows: Given some integer x, NearestPrime yields the prime number nearest to x that is not greater than x. ...
1
vote
2answers
44 views

Prove that $\{2k+5 \mid k\in \mathbb{Z}\} = \{2k+3 \mid k\in \mathbb{Z}\}$.

Prove that $\{2k+5 \mid k\in \mathbb{Z}\} = \{2k+3 \mid k\in \mathbb{Z}\}$. I know how to do $\{2k+5 | k\in \mathbb{Z}\} \subset \{2k+3 \mid k\in \mathbb{Z}\}$. What I'm having trouble doing is ...
0
votes
1answer
26 views

A question about non consecutive sum writing

I am very confused and I thank you in advance for your help about a very stupid question. I would write a summation sequence of non consecutive primes $a,b,c,d...$ greater than $3$ with a distance of ...
0
votes
0answers
36 views

any online video course for analytic number theory or elementary number theory?

All: I am looking for online video course on analytic number theory for self-study. On Youtube, there are a few seminars, but no complete course for a semester or a year. Can anyone point out if ...
0
votes
1answer
30 views

Definition of $0$ as given in G.B. Fine's book, “The Number System Of Algebra”.

I am reading G.B. Fine's book, "The Number System Of Algebra". He defines the number $a-b$ as the solution of the equation $a=x+b$, or the number satisfying the equation $(a-b)+b=a$. In article 13 he ...
1
vote
4answers
40 views

Upper limit for the Divisor function

For a a ponsitive inreger $n$, let $d(n)$ denote the number of divisors of $n$. I'm trying to prove that: 1) For $n>6$ we have $d(n)\leq\frac{n}{2}$; 2) For $n>12$ we have ...
2
votes
3answers
111 views

Find the last non-zero digit of $30^{2345}$

Find the last non-zero digit of $30^{2345}$ Source: Athena Healthcare Interview Questions
1
vote
1answer
27 views

Modular equation with non-integer numbers?

I was reading the book Homomorphic Encryption and Applications when I saw a modular equation involvind non-integer numbers. In short, on page 59 the book define the set $y$ as $\{y_1, y_2, .., ...
1
vote
1answer
16 views

Let p ∈ P be an odd prime. Show that the sum of the legendre symbol (a/p) for 0<a<p is 0.

First I note that $(a/p)$ cannot equal 0 because $0<a<p$. I have verified the statement for p =3, 5, and 7 by applying the formula: $$(a/p) = a^{(p-1)/2} mod(p)$$ $$3: 1 - 1 = 0$$ $$5: 1 - ...
1
vote
6answers
125 views

Are there numbers such that A + B = 10A+B? [closed]

I was just wondering, apart from zero,are there numbers where $A+B=10A+B$ (the number AB)?
2
votes
1answer
28 views

Given some large integer, is there way to construct a modulus such that the remainder that is below some threshold?

The proper context is integers too large for factorization to be computationally feasible, but, for the sake of illustration, the question is given an integer, such as 228483159, is there a procedure ...
1
vote
3answers
184 views

Intersection multiplicity of the curves

I want to find the intersection multiplicity of the curves $f(x,y)=x^5+x^4+y^2$ and $g(x,y)=x^6-x^5+y^2$ at the point $P=(0,0)$. That`s what I have tried: $f$ and $g$ have a common tangent, the ...
2
votes
2answers
35 views

In Zagier's one-sentence proof, why is S defined to be {(x,y,z)∈ℕ^3:x^2+4yz=p,p prime}?

I've looked at a very clear explanation of Zagier's proof (specifically, it can be found here:http://danielmath.wordpress.com/2012/12/26/one-sentence-proof/) but the first step still eludes me: why is ...
1
vote
1answer
32 views

Explanation of a bitwise XOR phenomenon

I have found an interesting phenomenon when using bitwise XOR: $$\begin{array} {ccccc} 134&& 48&& 14\\ \\ & 182&& 62& \\ \\ && 136 && ...
1
vote
2answers
50 views

How to solve $x^2 \equiv [1]$ in $\Bbb Z_5$

I would like to know how to solve $x^2 \equiv [1]\text{ in }\Bbb Z_5$? How to solve this kind of equation in general?
19
votes
3answers
2k views

Infer number of terms in sum, given the value of the sum

In preparation for a math contest my little brother's teacher gave him a nice little book full of interesting little math exercises. And whenever my brother got stuck, he asks me for help and we ...