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

learn more… | top users | synonyms (1)

0
votes
1answer
13 views

Prove that multiplication by an integer $a$ that is relatively prime to $n$ defines a bijection from $\mathbb{Z}_n-\{0\}$ to itself

If gcd$(a,n)=1$, then multiplication by $a$ defines a bijection from $\mathbb{Z}_n-\{0\}$ to itself. My working: If $n=p$ a prime, then we can use the Fermat's Little Theorem. If $n$ is not prime in ...
2
votes
1answer
58 views

Are primes less than the sum of divisors?

I am trying to prove that Let $p_n$ be the $n$th prime number, $\sigma (n)=\sum_{d|n}d$. Prove that $$\sigma(n) \le p_n$$ It seems obvious at first glance-to me, at least the sum of divisors of ...
5
votes
2answers
36 views

For any $a$ in $\Bbb Z$, prove that $6|a(a+5)(a+10)$

So I am given this question for my number theory and proof class: For any $a \in \Bbb Z$, prove that $6|a(a+5)(a+10)$. I've thought about a few different ways to approach this. I think I could ...
1
vote
1answer
38 views

Solve $\lfloor x \rfloor = ax+1$ for integral $a$

Solve $\lfloor x \rfloor = ax+1$, where $a$ is an integer. I have found the values of $x$ for $a=0$, $a=1$ and $a=-1$. But I don't know how to continue. How can I find the solutions for integral ...
1
vote
0answers
31 views

Infinitely many primes of the form $16n+1$? [duplicate]

As the title states I need to prove there are infinitely primes of the form $16n+1$ but I have absolutely no idea how to do it.
1
vote
2answers
23 views

Help me to understand question on Linear Congruence in simplest and elaborated way.

I came across the following congruence in which I have to get value of $x$. They devide it by $3$ which I understand how and multiply it by $7$ on both sides and proceeds further as shown by photo ...
0
votes
1answer
45 views

Exponentiation on the natural numbers. Prove the identities $n^{(m+k)}=n^m \cdot n^k$ and $n^{(m \cdot k)}=(n^m)^k$.

Moschovakis, Set theory, Chapter 5, Problem, x.5.3. Exponentiation on the natural numbers is defined by the following recursion on $m$: $n^0=1$, $n^{Sm}=n^m \cdot n.$ Show that it satisfies the ...
4
votes
1answer
53 views

Solving the Diophantine Equation $x^2 - y! = 2001$ and $x^2 - y! = 2016$

I had recently faced a problem: Solve the Diophantine Equation $x^2 - y! = 2001$. Solving it was quite easy. You show how $\forall y \ge 6$, $9|y!$ and since $3$ divides the RHS, it must divide ...
7
votes
1answer
100 views

how to calculate double sum of GCD(i,j)?

I stumbled upon a programming question which wanted me to calculate : $$G(n) = \sum _{i=1}^{n} \sum _{j=i+1}^{n} gcd(i, j).$$ now I wrote a code to solve this problem but it takes polynomial time to ...
-1
votes
0answers
22 views

If t divides the LCM of two non-zero integers, then the two integers divides t

Suppose that $k=LCM\left ( m,n \right ) \exists k \in \mathbb{Z} \forall m,n \in \mathbb{Z}$ and $\space t \mid k$ $\exists t \in \mathbb{Z}$ , Then, both m and n must divides t. Is the ...
0
votes
3answers
43 views

How many numbers less than 100 have the sum of factors as odd?

How many numbers less than 100 have the sum of factors as odd? Answer is 16 This question and explanation is taken from careerbless.com The link given derives the answer using some ...
1
vote
1answer
19 views

For any integers $a,b$ the relatively prime integers $m,n$ giving $am + bn = 0$ are unique.

I can prove for any integers $a,b$ that a choice of relatively prime $(m,n)$ gives $am + bn = 0$: 1) Set $m$ to $-b$ 2) Set $n$ to $a$ 3) Divide $m$ and $n$ by $d = gcd(a,b)$. 4) $m$ and $n$ are ...
0
votes
1answer
30 views

Find the smallest number of toys that person had

A person had a number of toys to distribute among children . At first he gave $2$ toys to each child , then $4$ , then $5$ ,and then $6$ , but was always left with one . But if he had given $7$ toys ...
0
votes
1answer
52 views

How do I prove 'For all integers a, there exists an integer b so that 3|a+b and 3|2a+b?

My approach is to divide the prove into 2 cases, where case1 is when its just 'a' and case 2 is when it is '2a'. Is that any close to being the correct proof?
1
vote
1answer
22 views

Constant angles and powers

One can verify without difficulty that for all triple $(a,b,c)$ of real numbers greater than $1$, with $a\le b\le c$, and for all positive integer $n$, the equality $$a^n+b^n=c^n\qquad (*)$$ ►it has ...
1
vote
2answers
29 views

Help me prove a modular congruence!

Show that $a^{42} \equiv 1 \pmod{1764}$ if $\gcd (a, 1764) = 1$. Use Euler's theorem. Hint: $1764 = 4 \cdot 9 \cdot 49$ Hint: if t is a common multiple of $\phi(m)$ and $\phi(n)$, where ...
3
votes
1answer
37 views

Solve this problem on functions

Let $f$ be a bijection from the set of non-negative integers to itself. Show that there exist integers $a$,$b$,$c$ such that $a < b < c$ and $f(a)+f(c)=2f(b)$. I don't know how to approach ...
5
votes
3answers
86 views

Proving that the only integer solution of $2x^2+3y^2=z^2$ is $(0,0,0)$

I'd like to prove that the only integer solutions of $$2x^2+3y^2=z^2$$ is $(0,0,0)$. By working in $\mathbb{Z}_2$ and $\mathbb{Z_3}$, I have gone as far as proving that in $\mathbb{Z}$, any integer ...
0
votes
0answers
17 views

Prove that among five consecutive positive integers… [duplicate]

Prove that among five consecutive positive integers there is one integer which is relatively prime to the other four. I tried assuming that it is false and then find a contradiction, but that din't ...
4
votes
3answers
46 views

Sum of number-of-divisors function equals $\sum_{j=1}^{n} \lfloor n/j \rfloor$.

I am trying to prove the identity $$t(1) + t(2) + \cdots + t(n) = \Big\lfloor \dfrac{n}{1} \Big\rfloor + \Big\lfloor \dfrac{n}{2} \Big\rfloor + \cdots + \Big\lfloor \dfrac{n}{n} \Big\rfloor,$$ where ...
0
votes
1answer
25 views

Infinitude of primes in logical notation [closed]

Can this formal statement about the infinitude of primes be improved (i.e. made shorter and/or more elegant and standard)? $$\#\left \{ m\in \mathbb{N } \backslash\left \{ 1 \right \} : \exists n ...
4
votes
2answers
102 views

Without using prime factorization, find a prime factor of $\frac{(3^{41} -1)}{2}$

Not sure how to go about this. Law of quadratic reciprocity and Euler's Criterion is recently learned material but I'm not sure how this applies.
2
votes
3answers
275 views

Proof using deductive reasoning

I need to deductively prove that the sum of cubes of $3$ consecutive natural numbers is divisible by $9$. I can prove deductively that they are divisible by $3$ but so far any combination I choose ...
2
votes
0answers
33 views

Is there anyway to find how many prime factors has a composite number without knowing them?

Let's call f(n) the function that gives us the number of different prime factors of a composite number n For example: f(24)=2 Let's call g(n) the function that gives us the number of prime factors of ...
4
votes
2answers
33 views

Primes of the form $(2p)^{2}+1$, $p$ prime, have $h^{2}+1$ as a prime divisor?

I'm an undergraduate student and I usually ask questions here about things I'm struggling with in my academical mathematical studies, but this particular question is actually more like a curiosity. ...
1
vote
1answer
20 views

divisibility theorem proof?

I have found in a book the proof for the divisibility problem that says: If $a$ and $b$ are integers and $b$ is not equal to zero, then there is a unique pair of integers $q$ and $r$ such that ...
3
votes
1answer
118 views

For which polynomials $f$ is the subset {$f(x):x∈ℤ$} of $ℤ$ closed under multiplication?

You surely know about the Brahmagupta–Fibonacci identity, $$(a_1^2 + b_1^2)(a_2^2 + b_2^2) = (a_1a_2 \pm b_1b_2)^2 + (a_1b_2 \mp a_2b_1)^2$$ which tells us that the product of two numbers, each of ...
0
votes
0answers
19 views

Pythagorean Triples $\mod{c}$

I have a quick question regarding modular arithmetic. If I have a Pythagorean Triple $(a, b, c)$, is it possible to consider this equation $\mod{c}$. That is to say, Is the implication $$a^2 ...
1
vote
0answers
14 views

computing difference between all pairs of numbers which is given in ascending order

What are the different ways with which we can compute difference between all pairs of numbers among given numbers in ascending order. Say we have x1,x2,x3.....x8 where X1 X2..X8 ARE IN ASCENDING ...
1
vote
1answer
16 views

Proof of $\sum_{j=1}^{p-1} \lfloor jq/p \rfloor = \frac{1}{2}(q-1)(p-1)$ Involving Pairing of Summands

I've seen the proof of the identity $$\sum_{j=1}^{p-1} \lfloor jq/p \rfloor = \frac{1}{2}(q-1)(p-1)$$ where $p$ and $q$ are coprime positive integers. This involves counting the remainders ...
1
vote
0answers
25 views

Squares in a second order linear recurrence of positive integers

Let the integer sequence $n_k$, ($k\ge 0$) be defined as $$ n_0=1$$ $$n_1=64$$ $$ n_k=38 n_{k-1}-n_{k-2}-90$$ How can one find the squares in such a sequence? Besides $ n_0=1^2, n_1=8^2$, we also ...
1
vote
0answers
32 views

Prove that $p=13$, given that $(p-1)/4$ and $(p+1)/2$ are prime. [duplicate]

Suppose $p$ is a prime such that $(p-1)/4$ and $(p+1)/2$ are also primes. Show that $p=13$. I thought about taking $p_1=(p-1)/4$ and $p_2=(p+1)/2$ and proving that there is only one possible case ...
1
vote
1answer
46 views

Prove that there does not exist integer solutions for the diophantine equation $x^5 - y^2 = 4$.

Prove that there does not exist an integer solution for the diophantine equation $x^5 - y^2 = 4$. It's obvious that $x$ and $y$ are of the same parity. We can also claim that if $x$ is odd, then ...
0
votes
0answers
25 views

Complete formalization of solutions to $a^2+b^2=c^2+k$ for fixed $k>0$

Is there a known complete formalization of solutions to $a^2 + b^2 = c^2 + k$ for a fixed constant $k>0$ similar to the one for primitive Pythagorean triples (i.e. $(a,b,c) = (m^2-n^2,2mn,m^2+n^2)$ ...
0
votes
0answers
34 views

Does Inverse of Phi(N) Mod (N) always exist?

Let N=pq where p and q are odd primes and let $\Phi(N)$ be Euler Phi function i.e. $\Phi(7) = 6$ since 6 numbers co-prime to 7 Does the inverse of $\Phi(N) Mod(N^2)$ always exist? It exists if and ...
0
votes
1answer
55 views

Explanation to Fermat's little theorem proof

Fermat's little theorem $\forall a \in \mathbb{Z}$ and every prime p. Then, $a^{p}\equiv a\pmod p$ $a=pm+r $ $\forall 0 \leq r<p$ Proof for $r\not\equiv 0:$ Then, $\forall r \in ...
2
votes
2answers
92 views

Is it divisible by $3^n$?

I need to prove that a number made up exactly $3^n$ $1$s and nothing else is a multiple of $3^n$. Well I think it is true that any number is a multiple of $3^n$ if the sum of its digits is. But I ...
-4
votes
2answers
145 views

Why is minimum solution example to $x^n + y^n = z^n$ comes in the form of three successive integers? [closed]

Can we prove or disprove this conjecture by elementary mathematics: If this is a true statement: $$x^n + y^n = z^n $$where $x, y, z, n$ are positive integers, then there must be a minimum integer ...
3
votes
0answers
62 views

When does $a^b\mid b^a$

Let $a,b >1$ be integers. When does $a^b \mid b^a$? Certainly if this is true then $a\mid b$ by considering $a$'s prime factors. (not quite convinced). Also then if $b$ is prime then $a=b$. ...
0
votes
1answer
75 views

Congruence - Number Theory

Prove that $2005^{2005}$ is not the sum of two perfect cubes. I have looked at some mods but none have given me anything useful as of yet. I looked at the usual mods such as $4, 5, 7, 11, 13$ but ...
0
votes
0answers
17 views

Proving the Well Ordering Property of $\mathbb{Z}$ by induction and prove the minimal element is unique.

I would like a verification of this proof. (Am I using induction?) Claim: $\mathbb{Z}$ is well ordered and there exists a unique minimal element. Assumptions: There are no repeated members in ...
0
votes
0answers
19 views

Number theory questio [duplicate]

I have studied for about 250 questions and there are many questions i can't take.. i considered but i don't know how to start... how can i solve this? In second question, there even hint.. Well ...
1
vote
1answer
44 views

Solving the equation $x^3+y^2=4x^2y$ over integers.

$$x^3+y^2=4x^2y$$ This is a quadratic in $y$, the discriminant of which must be $>0$ $$\implies 16x^4-4x^3>0$$ $$\implies x \text { belongs to } (-\infty,0) \cup (1,\infty)$$ (So we have ...
-1
votes
0answers
21 views

Unique factorization property 3i [duplicate]

I know about unique factorization And i think that it will be used in these kinds of question that Norm But i want to know the way of proving the K has unique factorizatiob property If it doesn't ...
1
vote
0answers
61 views

The sum of the greatest common divisors

What are the values for the positive numbers $a,b$ and $c$ can take the expression $$(a^2,b^2)+(a,bc)+(b,ca)+(c,ab)?$$ (Here $(u,v)=\gcd(u,v)$ - the greatest common divisor for $u\in \mathbb N, ...
0
votes
1answer
26 views

Fibonacci sequence property

I think its proof will be simple but. I dont know well When the difference of number of sequence in fibonnaci is 1 or 2, i know how to prove but this is not
0
votes
0answers
9 views

Explain following Congruences in elementry way

While studding David M Burton I am felling difficulties with Linear Congruence is there any another way expertise this area (online resources). And how can I show that $21x \equiv 49\ (mod\ 10)$ can ...
3
votes
0answers
43 views

Sum of integer squares with zero sum

This is something that I perhaps should know but don't. What is known about sums $\sum_{i=1}^k a_i^2$ subject to $\sum_{i=1}^k a_i=0$ where $a_i$ are integer? Specifically, which even integers can be ...
0
votes
1answer
18 views

Need an assistance with a specific step of a specific Division Algorithm proof

I'm trying to wrap my head around a Division Algorithm's proof. That is, Let $a, b \in \mathbb{Z}, a \neq 0$. Then there are unique $q,r \in \mathbb{Z}$ such that $b = qa + r, 0 \leq r < |a|$. ...
0
votes
1answer
30 views

If an integer $k$ is a divisor of an integer $n$, then $\frac{n}{k}$ is also a divisor of $n$?

A lot of these number theory ideas are popping up in my study of cyclic groups. In particular, in a note I came across. It is mentioned that: If an integer $k$ is a divisor of an integer $n$, ...