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

learn more… | top users | synonyms (1)

0
votes
1answer
26 views

$a^n-n^a \mid b^n-n^b$ for all large $n$

I just saw this question, which recalled me a similar one.. Problem. Find all integers $a,b>1$ such that $a^n-n^a$ divides $b^n-n^b$ for all integers $n$ sufficiently large.
1
vote
0answers
18 views

Image of Norm map via Quadratic Residue

Let $\zeta$ be one of $\{\zeta_6,\; i\sqrt2,\; i,\; \sqrt2,\; \sqrt3,\; \Phi\}$. For each of the primes $p$ below and each of the values of $\zeta$ listed, say whether $\pm p$ is in the image of the ...
4
votes
1answer
41 views

How to decide which moduli to check when solving a “polynomial” congruence?

Consider the following problem: Find all integer solutions to $y^2 = x^5 - 4$. The solution goes something like – check modulo 11, where $x^5 \equiv 0, \pm 1$, and then check cases to arrive at ...
1
vote
1answer
61 views

Solving a Diophantine equation: $y^x=x^{2007}$, $x$ and $y$ integers.

I found this Diophantine equation and to solve it I used the definition of logarithm but the solution doesn't require the use of logarithmic rules. I solved it in this way: $$y^x=x^{2007}$$ ...
4
votes
4answers
95 views

If $a,b$ are positive rational numbers and $\sqrt a+\sqrt b$ is rational, then both of $\sqrt a,\sqrt b$ are rational numbers

I'm trying to show that If $a,b$ are positive rational numbers and $\sqrt a+\sqrt b$ is rational, then both of $\sqrt a,\sqrt b$ are rational numbers. I squared the number $\sqrt a+\sqrt b$ ...
1
vote
2answers
33 views

Standard result for $\log(x)$

$$\sum_{1\leq m\leq x/d}\frac{1}{m}=\log(\frac{x}{d})+O(1)$$ I read this result in lecture papers I was going through and can't find anything about its origin. Is there a standard summation result ...
1
vote
1answer
27 views

Show that $ i \equiv j \pmod{p-1}$ and $p\nmid n$ then $n^j \equiv n^i \pmod p$

Let $p$ be prime. Show that $ i \equiv j \pmod{p-1}$ and $p\nmid n$ then $n^j \equiv n^i \pmod p$ I know that $i$ and $j$ have the same remainder when divided by $p-1$, and that's pretty much it. ...
1
vote
3answers
28 views

Divisibility of integers by integers

We are given a number $$K(n) = (n+3) (n^2 + 6n + 8)$$ defined for integers n. The options suggest that the number K(n) should either always be divisible by 4, 5 or 6. Factorizing the second bracket ...
3
votes
1answer
24 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
25 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 !
1
vote
2answers
24 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
30 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 ...
-4
votes
0answers
29 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
39 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
51 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
29 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
28 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
57 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
31 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.
7
votes
1answer
64 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
69 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
26 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
46 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
328 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 ...
21
votes
0answers
125 views
+50

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
38 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
46 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
3answers
144 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
169 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
361 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: ...
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
147 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
46 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
75 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 ...