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

learn more… | top users | synonyms (1)

0
votes
0answers
8 views

Solvability of the Diophantine equation $x^{2} - y^{2} = 4z^{n}$?

It is known that for every integer $z$ there are integers $x, y$ such that $x^{2} - y^{2} = z^{3}.$ In fact, given an integer $z$, taking $x := z(z+1)/2$ and $y := z(z-1)/2$ suffices. But how is the ...
0
votes
1answer
19 views

Solve in positive integers $a^2-b^2+4a=0$

Solve in positive integers $a^2-b^2+4a=0$ I tried considering the residues in mod4 but not so helpful. Any help/hint on how to approach this problem ? Thanks !
0
votes
2answers
16 views

Mistake in proof of sum of divisors function $\sigma(n)$

The proof derives the correct result, but I cannot see how the first equality is correct. To begin we use the formula $\sigma(n)=\sum_{d\mid n}d$ This is the first step in the proof: $$\sum_{1\leq ...
0
votes
1answer
27 views

Bitwise ops - The relationship between $a$, $b$, $a \wedge b$, $a \vee b$ and $a \oplus b$

In computer programming, the term bitwise operation is used to denote the use of boolean operators (and $\wedge$, or $\vee$, exclusive or $\oplus$) on corresponding bits of two numbers. Bits, in this ...
-2
votes
0answers
17 views

quadratic sequence [on hold]

For a quadratic sequence in form $y^2=x^2+2bx-d$, can it be shown that for some range of $x$ (say,$1\lt x_1\lt x_2\le b)$ there is at least one perfect square.Equations of the form cited give rise to ...
-4
votes
0answers
24 views

Finding the modulo of 801 [on hold]

If $d_{k}(m)$ is the number of divisor of m that are congruent to $k$ modulo $4$. How can I find $d_{1}(801)$ and $d_{3}(801)$ .
1
vote
3answers
35 views

Divergence of sum reciprocal of primes using Bertrand's Postulate

I have been trying to prove that the series of reciprocal of primes diverges by only using Bertrand's Postulate. Does anybody know if this is possible? Or is it the case that this postulate is not ...
1
vote
1answer
50 views

Prove summations are equal

Prove that: $$\sum_{r=1}^{p^n} \frac{p^n}{gcd(p^n,r)} = \sum_{k=0}^{2n} (-1)^k p^{2n-k} = p^{2n} - p^ {2n-1} + p^{2n-2} - ... + p^{2n-2n}$$ I'm not exactly sure how to do this unless I can say: ...
0
votes
1answer
28 views

Have you seen these integer factorization algorithms before?

I have two algorithms for finding two factors, $p$ & $q$, of a number $N$. The algorithms are (hopefully) obviously related. The pseudo-code for them follows: Algorithm 1 ...
2
votes
2answers
23 views

Doubling checking my understanding of these set relations

Just trying to make sure that my understanding of the set relations below is correct T1 = {x $\in$ $\Delta$ | for every y, (x,y) $\in$ R implies y $\in$ C} T2 = {x $\in$ $\Delta$ | there exists y, ...
0
votes
0answers
22 views

Is there an alternative encoding scheme to binary where similarity of pattern correlates with size of number?

If I compare binary for 7 111 and binary for 8 1000 there is no correlation between these two patterns that suggests that ...
2
votes
5answers
55 views

Last digits of sum $n!+m!$

Please, give me a hint Can the last four digits of the sum $n!+m!$ be 1990? Or, in other words, can one find such $n,m$ that $m!+n! \mod 10^4 = 1990$?
3
votes
1answer
27 views

Is there any solution to this quadratic Diophantine 3 variables equation?

Is it possible to find all positive integer triplets $(x,y,z)$ satisfying the parametric equation : $$x^2 + 2ax + y^2 + 2by = z^2 + 2cz$$ Here $a, b, c$ are fixed positive integers.
6
votes
1answer
60 views

If all the numbers $(1^\alpha,\,2^\alpha,\,3^\alpha,\,\dotsc)$ are integer, then $\alpha$ is an integer.

A theorem of Siegel asserts that If $\beta>0$ and $2^\beta,\,3^\beta,\,5^\beta$ are integers, then $\beta$ is an integer. The following result is a beautiful consequence of this theorem ...
3
votes
1answer
68 views

When does $2^{n}$ divide $3^{n}-1$

The title says it all. For what natural numbers n does 2^n divide $3^{n}-1$. By substituting values I can see that this happens for or n=1,2,4 but are there more?? I am not able to prove/disprove.
1
vote
2answers
24 views

Show $\sum_{1\leq n\leq x}\sum_{d\mid n}f(d)=\sum_{1\leq d\leq x}\sum_{1\leq m\leq x/d}f(d)$

I have been trying to get my head around this step in a proof, but havn't been able to, Question: Show $$\sum_{1\leq n\leq x}\sum_{d\mid n}f(d)=\sum_{1\leq d\leq x}\sum_{1\leq m\leq x/d}f(d)$$ ...
-1
votes
0answers
10 views

mensuration-Surfaces area and volumes

A sports goods manufacturing company engaged a party for supplying cardboard cylinder with their two lids for packaging badminton shuttle cocks. The terms are: a) Quantity of cylinders $5000$ b) ...
3
votes
2answers
42 views

If $m, n$ be positive integers, prove that $\phi(mn)=\phi((m,n))\phi([m,n])$, where $(m,n)=$ gcd of $m, n$ and $[m, n]=$ lcm of $m, n$.

If $m, n$ be positive integers, prove that $\phi(mn)=\phi((m,n))\phi([m,n])$, where $(m,n)=$ gcd of $m, n$ and $[m, n]=$ lcm of $m, n$. I have no idea to solve this question. Please help me to ...
1
vote
2answers
326 views

Aren't there obvious patterns in the primes that no one makes use of and what about this…

Let's take the sequence of naturals at or above two ($2, 3, 4, \dotsc$) and cross out just the primes $2$ and $3$, as well as all their multiples: $$\require{cancel}\cancel{2}, \cancel{3}, \cancel{4}, ...
1
vote
2answers
41 views

How to solve equations of the type: $\phi(n)=m$?

How to solve equations of the type: $\phi(n)=m$? I have, for instance, $\phi(n)=6$. I never saw that kind of questions. I would really appreciate any lead on it.
0
votes
1answer
38 views

Are $x$ and $y$ divisible by $n$, if so how do I prove it?

If $y$, $x$,are natural numbers, and $n$ is a prime number, $y = x + n$, $y>x>n$, and $y$ and $x$ are not coprime, is it true that $n$ is a divisor of both $x$ and $y$? If so could you please ...
0
votes
0answers
18 views

How do Quadratic Fields look on Complex Planes [duplicate]

I have spent a long time trying to seek some information of quadratic fields. Can someone show me a complex plane around the origin, with the points on the part of the complex plane which are ...
16
votes
0answers
84 views

Finding triplets $(a,b,c)$ such that $\sqrt{abc}\in\mathbb N$ divides $(a-1)(b-1)(c-1)$

When I was playing with numbers, I found that there are many triplets of three positive integers $(a,b,c)$ such that $\color{red}{2\le} a\le b\le c$ $\sqrt{abc}\in\mathbb N$ $\sqrt{abc}$ divides ...
0
votes
2answers
33 views

If every prime that divides $n$ also divides $m$, show that $\phi(mn)=n\phi(m)$ and $\phi(mn)=m\phi(n)$

If every prime that divides $n$ also divides $m$, show that $\phi(mn)=n\phi(m)$ and $\phi(mn)=m\phi(n)$. My attempt. As every prime that divides $n$ also divides $m$, this implies that $(m,n)=d$ ...
2
votes
1answer
37 views

Largest possible subset primes

Let $q$ be a Sophie Germain prime number, i.e. $2q+1=p$ is prime. Consider the set $\{1,2,3,\ldots,p-1\}$. Then what is the maximum size of a subset of this set, such that the subset contains no two ...
1
vote
0answers
35 views

Quadratic Field of $Q[√−1]$… [on hold]

Can someone show me a complex plane around the origin, with the points on the part of the complex plane which are quadratic integers in $Q[√−1]$. Another graph for $Q[√−3]$. And another for $Q[√−5]$. ...
1
vote
3answers
48 views

Prove that $\phi(n)=\frac{n}{2}$ iff $n=2^k$ for some integer $k\geq 1$

Prove that $\phi(n)=\frac{n}{2}$ iff $n=2^k$ for some integer $k\geq 1$ Attempt: Let $n=p_1^{\alpha_1}p_2^{\alpha_2}\dots p_k^{\alpha_k}$. Then $\phi(n)=\frac{n}{2} \implies ...
0
votes
1answer
22 views

Primes in Quadratic Fields with Norm less than 6

What are the primes in $\mathbb Q[\sqrt{−1}]$ which have norm less than $6$? Also what primes in $\mathbb Q[\sqrt{−3}]$ have norm less than $6$, and the primes in $\mathbb Q[\sqrt{−5}]$? Which of them ...
-4
votes
2answers
42 views

mathematical calculation problems [on hold]

I have been given the odd numbers $1, 3, 5, 7, 9, 11, 13, 15$ with the challenge of selecting any 3 numbers from the above, to produce the number $30$. We can perform any operation on numbers and ...
0
votes
1answer
22 views

Show that $ζ$ is a Quadratic Integer in $Q[\sqrt{−3}]$

So in the complex plane, there are three cube roots of one. Suppose we let $ζ$ be the cube root of one which has positive imaginary part. How can we show that $ζ$ is a quadratic integer in ...
6
votes
2answers
131 views

What is the ten's digit of $7^{7^{7^{7^7}}}$

What is the ten's digit of $\zeta=7^{7^{7^{7^7}}}$. I got this question while doing binomial theorem. I think that $7^4=2401$ and we only need $\zeta\pmod{100}$. All I could think of is already ...
1
vote
1answer
53 views

How Deficient a Number is? (Finding numbers having a certain deficiency)

This question was edited, in particular equations were corrected: A number N is said to be deficient by an integer $d$ if: $\sigma(N)=2N-d$ Note that powers of 2 are deficient by 1. While a prime ...
11
votes
1answer
166 views

A proof involving the Euler phi function

Problem: Let $\varphi$ be the Euler phi function, where for any $n \in \mathbb{Z^+}$, $\varphi(n)$ is the number of positive integers less than $n$ that are relatively prime with $n$. ...
3
votes
2answers
91 views

Diophantine Equations : Solving $a^2$ $+$ $ b^2$ $=$ $2c^2$

I was working through some number theory problems , when I came across the following question : Find all solutions of $a^2$ $+$ $b^2$ $=$ $2c^2$ My Solution (Partial) : We can rewrite the ...
10
votes
4answers
357 views

Understanding the trivial primality test

I'm reading an algorithms book and I came across a code example for a primality test. The problem is that I couldn't understand the condition for the for-loop: ...
1
vote
1answer
38 views

How can I find the common solution for the following linear congruences : [on hold]

How can I find the common solution for the following linear congruences : $1.)$ $x \equiv 5 \pmod {13}$ $x \equiv 3 \pmod {12}$ $x \equiv 2 \pmod{35}$ $2.)$ $x \equiv 2 \pmod{35}$ $x \equiv ...
7
votes
3answers
101 views

Irrational Numbers : Show that $0.1248163264…$ is irrational

I was working through some basic Number Theory Problems in Rosen and came across the following problem : Show that the real number $0.1248163264...$ represented in ...
0
votes
3answers
37 views

Diophantine Equations : Solve $a^2 + b^2 = 4c + 3$

I was working my way through some number theory problems , when I came across the following question : Find all solutions to the equation $a^2 + b^2 = 4c + 3$ My Solution (partial) : If ...
10
votes
4answers
142 views

Divisibility of $6^{2^n}+ 8^{2^n} +12^{2^n}+14^{2^n}+16^{2^n}+18^{2^n} +24^{2^n} +28^{2^n}+42^{2^n}$

Prove or disprove that for all natural $n$ $$6^{2^n}+ 8^{2^n} +12^{2^n}+14^{2^n}+16^{2^n}+18^{2^n} +24^{2^n} +28^{2^n}+42^{2^n}$$ is divisible by $259$. I tried to apply mathematical induction, but ...
-2
votes
3answers
51 views

basic word problem! [on hold]

Find the smallest number by which $108$ must be multiplied to give a multiple of $80$.
4
votes
3answers
35 views

Largest subset with no arithmetic progression

I am trying to find some weak bounds on the largest subset of a set, such that the subset has the property that it contains no three elements in arithmetic progression. The elements of the original ...
0
votes
3answers
41 views

Number of times $2^k$ appears in factorial

For what $n$ does: $2^n | 19!18!...1!$? I checked how many times $2^1$ appears: It appears in, $2!, 3!, 4!... 19!$ meaning, $2^{18}$ I checked how many times $2^2 = 4$ appears: It appears in, ...
1
vote
3answers
43 views

How to apply Chinese Remainder Theorem for $x$

If: $$x \equiv 0 \pmod{17}$$ and $$x \equiv -1 \pmod{9}$$ Then how is: $$x \equiv 17 \pmod{153}$$ I get that since $\gcd(9, 17) = 153 $ the solution will be $\pmod{153}$ but how do you get the $17 ...
2
votes
2answers
72 views

Let $m$ be the least positive integer divisible by $17$ whose digits sum to $17$. Find $m$.

Let $m$ be the least positive integer divisible by $17$ whose digits sum to $17$. Find $m$. $m$ is a 3 digit number (because this was an AIME problem). $$m \equiv 0 \pmod{17}$$ $$m \equiv 17 ...
5
votes
5answers
75 views

solutions such that a combination number is odd

Let $m$ be a positive integer. Given $m$, I want to find the largest $n$, $1\leq n\leq m$, such that $$m+n\choose n $$ is odd. Is there any standard theorems or results? Any references? Thanks!
2
votes
3answers
66 views

$a^2 = 2b^3 = 3c^5$ Find the smallest value of $abc$.

We have following equation: $a^2 = 2b^3 = 3c^5$ Where $a, b, c$ are natural numbers. Find the smallest possible value of product $abc$.
1
vote
1answer
24 views

Number of $q$-th residues modulo $n$

Let $q$ be a prime and $n\ge 2$ an integer. Moreover, define $f_q(n)$ as the number of $q$-th residues modulo $n$. Is it true that if $K$ is a positive constant then there exist infinitely many $n$ ...
1
vote
4answers
58 views

Is $\gcd(2^{2n}+1, 3)=1$?

Can any one prove that $2^{2n}+1$ and $3$ are relatively prime for any integer $n$? I tried with a Matlab program and computed this gcd upto $n= 25$. I got 1 for all of them. So I suppose that the ...
3
votes
13answers
2k views

Measure 11 liters using bottles of 16, 6, and 3 liters

This question has been bugging me for a day and finally I gave up and decided to ask the community for it so here's how it goes: Suppose we have 3 bottles with capacities of $16,6$ and $3$ liters, ...
0
votes
2answers
51 views

Construction of Natural Numbers

I am trying to prove that the natural numbers can be constructed from the product of a power of $2$ and an odd number. For all $n \neq 0$ in the natural numbers, $n = (2k+1)(2^p)$, where $k$ and $p$ ...