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

learn more… | top users | synonyms (1)

2
votes
1answer
57 views

number theory equation involving GCD

Fix the natural number $b$. How can I solve ? $$ x+\gcd(x,b) \equiv 0 \mod(b) $$ Can anyone please give me a reference? Best
2
votes
3answers
46 views

Help with a step in rearranging this problem

i'm working through the proof of this theorem; If $x$ is any real number other than $1$, then $$\sum_{j = 0}^{n -1} x^j = 1 + x + x^2 + \cdots + x^{n-1} = \frac{x^n-1}{x-1}$$ But i'm struggling with ...
1
vote
1answer
69 views

Numbers in a circle: how many sets of consecutive numbers have positive sum?

One hundred integers are written around a circle, and it is known that their sum is $1$. We will call a subset of several successive numbers a "chain". Find the number of chains whose members have ...
2
votes
1answer
66 views

Divisibility by Quadratics

The natural numbers $a$ and $b$ are such $a^2+ab+1$ is divisible by $b^2+ba+1$. Prove that $a = b$. I tried to algebraically manipulate it as follows: $(b^2 + ba + 1)k = a^2 + ab + 1$ $[b(a + ...
2
votes
3answers
460 views

Congruence classes: Find the inverse

I have the following problem: If $ [3640]$ is invertible in $\mathbb {Z}_{7297}$ then determine its inverse. Okay. The first thing I thought was: $$3640x\equiv 1 \pmod{7297}$$ But isn't there ...
2
votes
2answers
66 views

Number of solutions in a finite field

let $F$ be a field of $p^b$ elements, $p$ prime and $b \in \mathbb{N}$. Suppose I have $(a_1, a_2, \ldots, a_s) \in F^s$ and an equation $$ 0 = a_1 x_1 + \dots + a_s x_s. $$ I was wondering if anybody ...
0
votes
2answers
57 views

Explanation of $\equiv$, and which of these statements involving it are true?

I am not familiar with this three lines equal sign and reading about it didnt really help with the original problem, which is: From the options below choose up to two that show correct solutions ...
1
vote
2answers
101 views

Show that $\sum\limits_{p \leq x} \frac{1}{p}$ ~ ${\log\log{x}}$ when ${x \to \infty}$ (here p is a prime)

I saw that some of you were upset over my last question, so I decided to ask a more interesting question: Show that $\sum\limits_{p \leq x} \frac{1}{p}$ ~ ${\log\log{x}}$ when ${x \to \infty}$ (here ...
2
votes
0answers
62 views

Number of decimal places to be considered in division

This must be a basic question. But i need some help. What is the number of decimal places that needs to be considered normally in division operations in order to represent the dividend value as a ...
1
vote
2answers
68 views

Calculate the limit $\lim_{x \to \infty} \ \frac{1}{2}\sum\limits_{p \leq x} p \log{p}$ (here p is a prime)

Calculate the limit $\lim_{x \to \infty} \ \frac{1}{2}\sum\limits_{p \leq x} p \log{p}$ (here the sum goes over all the primes less than or equal to x) using the Prime Number Theorem. I think I've ...
2
votes
0answers
197 views

Looking for proof-without-words of Bezout's identity

I'm looking for a "proof-without-words" of Bezout's identity (for integers). Does anyone know of one?
1
vote
3answers
440 views

The smallest positive integer in the set $\{24u+60v+200w : u,v,w \in \Bbb Z\}$is given by which of the following number?

I am stuck on the following problem: The smallest positive integer in the set $\{24u+60v+200w : u,v,w \in \Bbb Z\}$is given by which of the following number? The options are: ...
0
votes
5answers
94 views

Help me get the Divisor

I want to divide a particular number with $4,7,$ and $13$, but I want to get the remainder as $1,2$ and $4$ accordingly. Could you please help me get the number (If feasible at all) and please explain ...
6
votes
3answers
193 views

$(4k-1)^2 +(4k)^2$ is a perfect square

Let $k$ be strictly bigger than 1. Is there any integer k such that $(4k-1)^2+(4k)^2$ is a perfect square? My computation shows that there are infinitely many such $k$, namely those arising from the ...
0
votes
2answers
49 views

Translation of; If X is any real number other than 1, then…

i've just started reading a book on number theory and am trying to follow along with the example proofs of theorems. I've not had too much trouble once I have managed to "translate" the mathematical ...
1
vote
2answers
292 views

Determining the smallest possible value

If both $11^2$ and $3^3$ are factors of the number $a \times 4^3 \times 6^2 \times 13^{11}$, then what is the smallest possible value of a? IS there any trick to answer this type question quickly? ...
9
votes
2answers
185 views

Polynomials mapping factorials to factorials

I'm looking for all polynomials $P(x)$ with integer coefficients such that for every $n \in \Bbb N$ there is an $m \in \Bbb N$ such that $P(n!)=m$!. The only solutions seem to be the constant ...
1
vote
1answer
69 views

Polynomial whose only values are squares

Given a polynomial $ P \in \Bbb Z [X] $ such that, $ P (x)$ is the square of an integer for all integers x, is $ P $ necessarily of the form $ P (x)= Q (x)^2$ with $ Q \in \Bbb Z [X]$?
6
votes
2answers
184 views

Prove that $(3+5\sqrt{2})^m=(5+3 \sqrt{2})^n$ has no positive integer solutions?

Is my proof ok? I set $b=3+5 \sqrt{2}$, so that we have $b^m=(b+2-3 \sqrt{2})^n$ , or $b^m=(b+\sqrt2(\sqrt2- 3))^n$. Since $RHS<LHS$, $n>m$ . However, from what we know about binomial ...
1
vote
2answers
36 views

Question about modular arithmetic and divisibility

If $$a^3+b^3+c^3=0\pmod 7$$ Calculate the residue after dividing $abc$ with $7$ My first ideas here was trying the 7 possible remainders and then elevate to the third power $$a+b+c=x \pmod 7$$ ...
0
votes
1answer
69 views

The sum of consecutive digits

a) Find the natural numbers ${\overline{ab}}$ such that ${\overline{ab}}= a+(a+1)+...+b$. b) Exist natural numbers ${\overline{abc}}$ such that ${\overline{abc}} = a+(a+1)+...+{\overline{bc}}?$; ...
1
vote
0answers
35 views

A Greatest Common Divisor Property [duplicate]

Show that: If $c|a^m-1$ and $c|a^n-1$ then $c|a^{gcd(m,n)}-1$
5
votes
2answers
417 views

On the number of quadratic residues $\pmod{pq}$ where$p$ and $q$ are odd primes.

I have read that the formula for the number of quadratic residues $\pmod{pq}$ for odd primes $p$ and $q$ is $\frac{(p-1)(q-1)}{4}$. Is this the case, and if it is, why is it the case and how would one ...
0
votes
1answer
613 views

Questions based on the greatest integer and fractional part functions

If $\displaystyle x = \left[\frac{3^{31}+2^{31}}{3^{29}+2^{29}}\right]$, then $x = $ If $x\left[x\left[x \left[x\right]\right]\right] = 2013$, then $x = $ If $\{x^2\}+\{x\} = 1$, then $x = $ My ...
2
votes
1answer
79 views

Why inverse modulo exponentiation is harder than inverse exponentiation without modulo

I am new to number theory. I read in cryptography inverse modulo exponentiation is used because it is hard. But I couldn't understand the advantage of it over inverse exponentiation without modulo. ...
-4
votes
3answers
524 views

why can't we divide by zero ?! [duplicate]

in arabic sites which is interested in maths , i find many topics like ,here is a proof that 0=2 . and we answer that the proof is wrong as we can't divide by zero . but i really wonder , why ...
14
votes
3answers
281 views

Showing that $1^k+2^k + \dots + n^k$ is divisible by $n(n+1)\over 2$

For any odd positive integer $k\geq1$, the sum $1^k+2^k + \dots + n^k$ is divisible by $n(n+1)\over 2$. I used induction principle for the solution but cannot prove it. I took $P(k) = ...
1
vote
2answers
91 views

Solving for $a,b,c,d$ where $a^2 + b^2 + c^2 + d^2 = 630^2$

How could one solve for $a,b,c,d$ where: $$a^2 + b^2 + c^2 + d^2 = 630^2,\ a>b>c>d$$ $a,b,c,d$ squared is equal to the square of $630$, and $a$ is larger than $b$, and so forth. $a,b,c,d$ ...
0
votes
1answer
44 views

not able to get the divisor

I faced one issue. The issue is as follows. I want to divide a particular number with 7,9,11 but in every case i want to get the remainder as 1,2 3 accordingly. Could you please help me get the ...
4
votes
1answer
165 views

Number Theory: Determine $a$ and $b$ satisfying divisor relationships

Determine integers $a$ and $b$ such as : $$a|b^2 \text{ and } b|a^2 \text{ and } (a+1) |(b^2+1)$$ I had tried to create a system , but I don't think that is the way to solve this problem Thanks. ...
3
votes
4answers
254 views

What is $2012^{2011}$ modulo $14$?

$$2012^{2011} \equiv x \pmod {14}$$ I need to calculate that, all the examples I've found on the net are a bit different. Thanks in advance!
7
votes
2answers
786 views

Given that $xyz=1$ , find $\frac{1}{1+x+xy}+\frac{1}{1+y+yz}+\frac{1}{1+z+xz}$?

I think I solved this problem, but I don't feel $100$ percent sure of my solution. We have: $xy=\large {\frac 1z}$ $xz=\large \frac 1y$ $yz=\large \frac 1x$ So let's substitute these into our sum: ...
4
votes
1answer
77 views

Symmetry in reduced residue systems

This may be a stupid question, but it looks to me like the reduced residue systems modulo N are symmetrical about N/2; that is to say, that the there is the same number of integers not divisible by a ...
4
votes
2answers
94 views

Prove that $\sum_{i=1}^{m-1} i^k$ is divisible by $m$

Prove that $\sum\limits_{i=1}^{m-1} i^k$ for odd numbers $m,k \in \mathbb{N}$ is divisible by $m$. Because $m \mid m^k$, it is equivalent to the following: Prove that $m \mid ...
6
votes
4answers
299 views

Greatest integer $n$ where $n \lt (\sqrt5 +\sqrt7)^6$

I'm really not sure how to do this. I factored out a power of $3$ and squared so that I have $2^3 (6+\sqrt{35})^3 \gt n$ , and I know that if I can prove that $12^3-1 \le (6+\sqrt{35})^3 \lt 12^3$ I ...
2
votes
1answer
429 views

Peano Axioms natural numbers, total order, uniqueness of addition and multiplication

Could you tell me how to prove the following? $(1)$ There exists the unique operation of addition : $+ \ : \ \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}$ such that $n+0=n$ and $n+ \sigma(m) ...
0
votes
3answers
131 views

Quadratic residues, mod 5, non-residues mod p

1) If $p\equiv 1\pmod 5$, how can I prove/show that 5 is a quadratic residue mod p? 2) If $p\equiv 2\pmod 5$, how can is prove/show that 5 is a nonresidue(quadratic) mod p?
2
votes
3answers
242 views

If $p$ is congruent to $2 \pmod 3$, how can I prove that all $a$, $1 \le a \le p-1$ are cubic residues $\mod p$?

If $p$ is congruent to $2 \pmod 3$, how can I prove that all $a$, $1 \le a \le p-1$ are cubic residues $\mod p$? Here's what I've done: $1^3$ congruent to $1 \pmod p$ thus, 1 is a cubic residue, ...
8
votes
1answer
307 views

The product of two natural numbers with their sum cannot be the third power of a natural number.

I wanted to know, how can i prove that the product of two natural numbers with their sum cannot be the third power of a natural number. Any help appreciated. Thanks.
1
vote
0answers
50 views

How to build $\operatorname{Hom}(\mathbb{Z}_p^*,\mathbb{Z}_{pq}^*)$ without solving DLP?

For given two distinct primes p and q, I want to construct all homomorphisms from the multiplicative group $\mathbb{Z}_p^*$ to the multiplicative group $\mathbb{Z}_{pq}^*$. Thanks to Jyrki ...
2
votes
1answer
397 views

Prove “casting out nines” of an integer is equivalent to that integer modulo 9

Let $s(x)$ be an abstraction for casting out nines of integer $x$. For all integers $x$, prove $s(x) \equiv x$ mod $9$ I'm not asking for an answer more of a way to attack this problem. Can't think ...
2
votes
2answers
902 views

For $n>3$ show that the integers $n$, $n+2$, and $n+4$ cannot all be prime

Okay so the solution I am given states that the division algorithm $\implies p=3k+1$ or $p=3k+2$ for some $k \in Z$ and $p \neq 3$. Can anyone explain why $p$ has to be $3k+1$ or $3k+2$? I can't ...
0
votes
2answers
39 views

Explanation of this step in a modular arithmetic problem

The multiplicative inverse of $5$ is $7$, when using mod $34$. $$\begin{align*} 5\cdot x&=3\\[0.1in] 7\cdot 5\cdot x &=7\cdot 3\\[0.1in] 1\cdot x &=7\cdot 3\\[0.1in] x&=21 ...
1
vote
0answers
69 views

Simplify $\frac{[m+n-1]!}{[m]![n]!}$ where $[k]=x^k-x^{-k}$ and $[k]!=[2][3]…[k]$.

Adopting the notation $[k] = x^k - x^{-k} $ and $[k]! = [2][3]...[k]$ (note that $[1]$ is omitted), and letting $m,n$ be two integers greater than $1$ such that $n>m$ and $gcd(m,n)=1$, would it be ...
5
votes
2answers
275 views

can all triangle numbers that are squares be expressed as sum of squares

I'm not sure if this is just a subset of Which integers can be expressed as a sum of squares of two coprime integers? which in turn points to ...
1
vote
2answers
68 views

How many divisors can $bx$ have, given the number of divisors of $b$ and $x$?

May I ask you for a little help about a problem from number theory: The numbers $x$ and $b$ have exactly 15 resp. 3 divisors. How many divisors could the numbers i) $ 7x$, ii) $ 6x$, iii) $ ...
10
votes
2answers
743 views

Factoring a number of complex integers?

Say you are given a number (ex: $377$) and you express it in a form that allows you to factor it over the complex integers: Notice, $377 = 16^2 + 11^2$ Thus: $(16 + 11i) $ and $(16 - 11i)$ Are ...
6
votes
3answers
1k views

Derivation of Pythagorean Triple General Solution Starting Point:

I was reading on proof wiki about the derivation of the general solution to the pythagorean triple diophantine equation: $$ x^2 + y^2 = z^2, $$ where $x,y,z > 0$ are integers. I came across the ...
4
votes
4answers
251 views

Mathcounts 2013 state sprint round #14

How many ways can all six numbers in the set $\{4, 3, 2, 12, 1, 6\}$ be ordered so that $a$ comes before $b$ whenever $a$ is a divisor of $b$?
3
votes
0answers
459 views

Confusing proof of brun's theorem?

I read Brun's proof of Brun's theorem here : http://gallica.bnf.fr/ark:/12148/bpt6k486270d/f110.image (and the following pages) and here http://gallica.bnf.fr/ark:/12148/bpt6k486270d/f138.image ...