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

learn more… | top users | synonyms (1)

0
votes
1answer
18 views

Show that there is a large value

Suppose not all 4 integers, $a, b, c, d$ are equal. Start with $(a, b, c, d)$ and repeatedly replace $(a, b, c, d)$ by $(a - b, b - c, c - d, d - a)$. Then show that at least one number of the ...
1
vote
1answer
21 views

Proving divisibility of $\sum\limits_{r=1}^{p-1} {r^{p^n}}$ by p.

Let $p>2$ be an odd number and let $n$ be a positive integer. Prove that $p$ divides $${\sum\limits_{r=1}^{p-1}{r^{p^n}}}$$ My Proof: From multinomial expansion, we know that $${(1 + 2 + 3 + ... + ...
2
votes
1answer
18 views

How to find cubic residues $\bmod p$ using WolframAlpha?

How to find cubic residues $\bmod p$ using WolframAlpha? Just type in "quadratic residues modulo p" and you're done, but typing in "cubic residues modulo p" does nothing. Logically, "x^3 ...
2
votes
1answer
23 views

Inequality which is true for almost every n

In my assignment I have to prove the following statement: Let $l$ be a natrual number. Prove that for almost every $n$ the following inequality is true: $n\lt\sqrt{n ^ 2 + l}\lt n+1$ I chose to ...
6
votes
2answers
69 views

$1+\frac{1}{2} +\frac{1}{3} +…+\frac{1}{p-1} =\frac{a}{b}$

Let $p\gt 3$, be a prime number and $1+\frac{1}{2} +\frac{1}{3} +...+\frac{1}{p-1} =\frac{a}{b}$ when $a,b\in \mathbb N$ and $gcd(a,b)=1$. prove that $p^2|a$. I proved that $p|a$, but I cant ...
2
votes
2answers
32 views

If $2^{12^{7}+3}\equiv x \pmod{36}$ then what is the value of $x$?

If$$2^{12^{7} + 3} \equiv x \pmod{36}$$then what is the value of $x$ ? We have , $$2^5 \equiv - 4 \pmod{36}$$ $$\implies2^{10} \equiv16 \pmod{36}$$$$\implies2^{12} \equiv - 8 ...
2
votes
0answers
25 views

Can I use integer frequencies in quadratic intervals to set a lower bound for primes?

I want to find out if the following arithmetic approach could produce a backdoor proof of Legendre’s Conjecture. It hinges on two assumptions, which are what I’m asking about, but I need to explain ...
0
votes
1answer
29 views

Why is $2(5u_p)^2\equiv (1+5^p)+4 \bmod 2p-1$?

Definition: $u_1=u_2=1$ and $u_{n+1}=u_{n}+u_{n-1}$ for $n\ge 2$. Suppose $p \ge 7$ is a prime for which $p\equiv 2 \bmod 5$ or $p \equiv 4 \bmod 5$. If $2p-1$ is also a prime, then how can I ...
1
vote
0answers
36 views

On the second part of solution of a question due to Erdos

Problem. Let $a_1<a_2<\dotsb<a_n\le 2n$ be a sequence of positive integers. Then $$ \min [a_i,a_j]\le 6\left(\Big[\frac n2\Big]+1\right), $$ where $[a_i,a_j]$ denotes the least ...
1
vote
2answers
36 views

Properties of Greatest Common Divisors

I really want to have help verify these properties of GCD: Let $s,t \in \mathbb{Z}$ and $m,n$ be positive integers with $m|n$. If $\gcd(t,n)|\gcd(s,n)$, then $\gcd(t,m)|\gcd(s,m)$. If ...
2
votes
1answer
59 views

How is Z$/n$Z isomorphic to Z$_n$?

Let $n$Z be the set of integer multiples of $n \in$ Z. Can someone explain how Z$/n$Z is isomorphic to Z$_n$? Specifically, what is the function that establishes the isomorphism and how can we be ...
0
votes
1answer
31 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
20 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 ...
5
votes
2answers
51 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
97 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
28 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
29 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
30 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
66 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
47 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 ...
24
votes
0answers
137 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
47 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 ...