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

learn more… | top users | synonyms (1)

3
votes
0answers
108 views

Show that the phi function is multiplicative $\phi(mn) = \phi(m)\phi(n)$ [duplicate]

Show that the phi function is multiplicative $$\phi(mn) = \phi(m)\phi(n)$$ Any nice way to prove this without using induction ? The textbook proof looks bit awkward to me, so I am trying to see if ...
2
votes
2answers
88 views

What is the remainder when $12^{39} + 14^{39}$ is divided by $676$?

I tried following but then I got stuck $676 = 26*26$ $12^{39} + 14^{39}$ is divisible $26$ for sure since $a^n + b^n$ is divisible by $(a+b)$ when $n$ is odd. But what to do next?
0
votes
1answer
31 views

Euclidean algorithm for two poloynomials

Find the $gcd(x^8, x^6+x^4+x^2+x+1)$ using the euclidean algorithm. $x^8 = (x^2)(x^6+x^4+x^2+x+1)+(-x^6-x^4-x^3-x^2)$ $(x^6+x^4+x^2+x+1)=(-1)(-x^6-x^4-x^3-x^2)+(-x^3+x+1)$ ...
-1
votes
6answers
82 views

Proving $2^{2n}-1$ is divisible by $3$ for $n\ge 1$

So I decided to use induction. First, I started with my base case, $P(1) = 2^{2(1)}-1=3,$ so it's true. That means if $n = k$ is true, then $n = k+1$ is true also. So, $P(n+1)-P(n)$ would also be ...
1
vote
1answer
71 views

Given integers $a$ and $b > 0$, show that there exists a unique integer -

Given integers $a$ and $b > 0$, show that there exists a unique integer $r$ with $0\le r\lt b$ satisfying $a = \left\lfloor \dfrac{a}{b} \right\rfloor b + r$ I am familiar with the Euclidean ...
3
votes
2answers
59 views

For which $p$ and $q$ polynomials $x^q-1$ and $(x+1)^q-1$ are coprime in $F_p[x]$?

It easy to prove that polynomials $x^q-1$ and $(x+1)^q-1$ are coprime in $\mathbb{Q}[x]$ if $(q,6)=1$, since they don't have a common zero in $\mathbb{C}$, this can be seen geometrically. My question ...
3
votes
4answers
127 views

Why is it impossible to find natural numbers $a$ and $b$ such that $12b^2=a^2$?

This was a question in the exercises for an EdX course by Prof Starbird on Effective Thinking through Mathematics which was long over, but I am working through the course at my own pace. I feel that ...
4
votes
0answers
102 views

Is this a valid statement that would imply the Collatz Conjecture?

Let $f$ denote the Collatz transformation: $f(x) = \left\{ \begin{array}{ll} {x\over 2} & \quad x\equiv 0 \mod 2 \\ 3x+1 & \quad x \equiv 1\mod 2 ...
1
vote
5answers
79 views

prove if a|b and b|a then $a = \pm b$

Fairly basic I guess. Attempt: $a\neq\pm b \Rightarrow a\nmid b \vee b \nmid a$ let $a = \pm b + d, d\in \mathrm{Z} \wedge d\neq 0$ then $a\mid b \Rightarrow b\nmid a$ and $b\mid a \Rightarrow ...
5
votes
1answer
81 views

infinitely many primes $p$ such that $p$ divides $a_{1}^k+a_{2}^k+…+a_{n}^k$

Consider the positive integers $a_{1},a_{2},...,a_{n}$, not all identical ($n>1$). Prove that there are infinitely many primes $p$ such that $p$ divides $a_{1}^k+a_{2}^k+...+a_{n}^k$ for some ...
2
votes
2answers
242 views

Solutions of Diophantine equation

Does there exists any other solutions of the following Diophantine equation $$zx^2 +xy^2 +yz^2 =xyzt .$$ I found that $$(x,y,z,t) =(s,s,s,3) ,(x,y,z,t)=(s,2s,4s ,5)$$ where $s\in\mathbb{N}$ are ...
0
votes
3answers
140 views

Particular number is divisible by 11

Let $\mathcal{N} \ $ be a natural number of the form $\mathcal{N}=\textrm{dcba}$ ($a$ being the number of units $b$ the tens digit $c$ the hundreds digit and $d$ the thousands digit). On what ...
0
votes
1answer
49 views

Lower bound on $| \lceil a \rfloor b- a\lceil b \rfloor|$

let $\lceil a \rfloor$ be the nearest integer function. Is there a nice lower bound on the expression: \begin{align} | \lceil a \rfloor b- a\lceil b \rfloor| \end{align} Thank you
1
vote
1answer
41 views

Multiplicative submonoid: an exercise

Here's my problem: (a) Show that the set of integers, which can be written as $a^2+ab+b^2$ for some $a,b \in \mathbb{Z}$ is a multiplicative submonoid of $\mathbb{Z}$; (b) Explain how all ...
5
votes
2answers
234 views

How many solutions are there for the congruence $x^{14}+x^7+1 \equiv 0 \; (\text{mod } 343)$?

I have another question for you: Tell how many solutions does the congruence $x^{14}+x^7+1 \equiv 0 \; (\text{mod } 343)$ and compute at least one of them. Does this kind of exercise have a ...
1
vote
1answer
56 views

Nearest Integer function

Suppose $x \in \mathbb{R}$, suppose $x>1$ and $a \in (0,1]$. Also, let $\lceil \cdot \rfloor$ be the nearest integer function. How can I factor: $\lceil ax \rfloor=???$ Is $\lceil ax ...
2
votes
1answer
67 views

May I have a hint for this gcd problem?

I am trying to prove the following: $$(2^a - 1, 2^b - 1) = 2^{(a,b)} - 1 \ \ \ \forall a,b \in \mathbb{N} $$ Where: $$ (a,b) := \gcd(a,b) $$ So far I have tried dividing $2^a-1$ by $2^b-1$ ...
0
votes
2answers
307 views

Reciprocal of 81 being the sequence of all natural numbers?

According to this document: http://www.answering-christianity.com/fakir60/81.htm describing the theory of scientist Peter Plichta, the reciprocal of 81 is: the ...
0
votes
2answers
47 views

Greatest Common Divisor Problem X

I having trobles troubles solving this problem. If we know that $(a,p^2)=p$ and $(b,p^3)=p^2$, find $(ab,p^4)$ and $(a+b,p^4)$. That is all I know. I suppose that, because this is number theory ...
2
votes
2answers
88 views

general form in congruence

Could we generalize this example of congruence issue for $x,n \in \mathbb{Z}_*$? $$ 1+x+\cdots + x^{n-1}\equiv n \pmod {x-1} $$
2
votes
2answers
111 views

congruence issue

I need to understand why this : $$(1+4+\ldots+4^{n−1})\equiv n \pmod3$$ Is that because \begin{align} 1&\equiv -2 \pmod3\\ 4&\equiv 1 \pmod3\\ 4^{2}&\equiv1 \pmod3\\ ...
4
votes
3answers
580 views

Shift numbers into a different range

I was wondering how can I shift my data that fall between a range lets say [0, 125] to another range like [-128, 128]. Thanks for any help
3
votes
2answers
153 views

Find the 6 Digit Number

$N$ is a 6 digit Natural number such that its sum of the digits is $43$. Find $N$ if Exactly One of the statements below is False: $(1)$ $N$ is a Perfect Square $(2)$ $N$ is a Perfect Cube $(3)$ N ...
0
votes
4answers
79 views

Solve $c^2-b^2-a^2=2N$

Is there anyone that can help solving this equation: $c^2-b^2-a^2=2N$ where $a,b,c,N$ are natural numbers. Edit: We need to express $a,b,c$ for a certain $N$. Regards
54
votes
4answers
3k views

Does the string of prime numbers contain all natural numbers?

Does the string of prime numbers $$2357111317\ldots$$ contain every natural number as its sub-string?
0
votes
2answers
88 views

If a prime $p\mid b$ and $a^2=b^3$, then $p^3\mid a$

I have an exercise that I don't know how to solve. I tried to solve it in many ways, but I didn't get any progress in proving or disproving this... The exercise is: Prove or disprove: if $p$ is a ...
4
votes
1answer
265 views

How to mark rational points on a sphere

I found this picture on mathoverflow, which I find very intriguing and so I like to know how to draw such an image with a simple computer program. To calculate the rational point, I can draw a line ...
2
votes
1answer
102 views

decomposition into three squares

Doing a coding assignment. And it's basically having a user enter $n$. Then I need to provide (If it exists) $$n = x^2 + y^2 + z^2.$$ Not really sure how to approach this. Any ideas?
1
vote
1answer
636 views

Proof of Floyd Cycle Chasing (Tortoise and Hare)

I am looking for a proof of Floyd's cycle chasing algorithm, also referred to as tortoise and hare algorithm. After researching a bit, I found that the proof involves modular arithmetic (which is ...
4
votes
1answer
38 views

Maximum operation order for a set of integers

Say we are given the positive integers $[1,1,2,2,3]$ We want to know what the maximum number is using only the operators $+$, $\times$. For this set the maximum operation is ...
1
vote
3answers
61 views

Greatest value of digits from adding numbers

$\begin{array} &&N&R\\ +&R&N\\\hline A&B&C \end{array}$ The addition problem above is correct. If N, R, A, B, and C are different digits, what is the greatest possible ...
2
votes
4answers
248 views

The final digit of fourth powers

I am working on "Elementary Number Theory" By Underwood Dudley and this is problem 13 in Section 4. The question is "What can the last digit of a fourth power be?" I got the correct answer but I'm ...
3
votes
0answers
56 views

Combinatorial interpretation of an equality

In a recent project, I came up with the following equality which turned out to be extremely useful for counting conjugacy classes in certain division algebras (I won't go into the details here, it's ...
3
votes
1answer
82 views

Any nice way to find number number of single digit ordered pairs $(a, b)$ such that $a!b! \gt a!+b!$

I have listed them all by brute force : a = 0,1 : no solutions a = 2 : b = 3,4,5,...9 c = 3 : b = 2,3,4...9 I'm wondering if there is a clever approach to ...
4
votes
2answers
111 views

Prove $\frac{ab}{1+c^2}+\frac{bc}{1+a^2}+\frac{ca}{1+b^2}\le\frac{3}{4}$ if $a^2+b^2+c^2=1$

Ff $a,b,c$ are positive real numbers that $a^2+b^2+c^2=1$ ,Prove: $$\frac{ab}{1+c^2}+\frac{bc}{1+a^2}+\frac{ca}{1+b^2}\le\frac{3}{4}$$ Additional info: I'm looking for solutions and hint that ...
6
votes
3answers
173 views

Does the sum of the reciprocals of all primes of the form $4k+1$ converge?

Let $S=\{p\in \mathbb{Z}^+ : p\ \text{is prime and}\ p\equiv 1 \mod \ 4\}.$ Is $\displaystyle\sum_{p\in S}\frac{1}{p}$ finite or infinite, and where can I find more information about it?
0
votes
1answer
64 views

The number of prime divisors of any number

How can one show that the number of prime divisors of any number less than $2^n$ is at most $n$.
5
votes
2answers
113 views

How to solve the congruence $x^{59} \equiv 604 \pmod{2013}$?

$$x^{59} \equiv 604 \pmod{2013}$$ Could somebody give me any clue? I have no idea how to start. I see that $59$ is prime.
2
votes
2answers
96 views

Irrationality of $\sqrt{3}$ [duplicate]

No doubt an easy question: I'm trying to follow Wikipedia's (second) proof of the irrationality of $\sqrt{3}$ and it relies on the notion that since $3n^2 = m^2$ is divisible by 3 then so is $m$. Why ...
-1
votes
3answers
82 views

Solve the diophantine equation $ ax+by=xyc$

Let $a,b,c$ be non-zero co-prime integers such that $a+b \neq c$, and $ x.y\neq 0$, solve the diophantine equation $ ax+by=xyc$.
0
votes
2answers
62 views

Solve this number theory problem without plugging in

$a>b$ $b<c$ $a=2c$ If a,b, and c represent different integers in the statements above, which of the following statements must be true? I. $ac>b^2$ I know that the above statement is true ...
4
votes
2answers
133 views

Is there an integer $N>0$ such that $\varphi(n) = N$ has infinitely many solutions?

Let $\varphi: \mathbb{N} \to \mathbb{N}$ be the totient function. Is there an integer $N > 0$ such that there are infinitely many integers $n > 0$ such that $$\varphi(n) = N?$$
1
vote
0answers
56 views

Are (odd) perfect numbers divisible by a repdigit (in another base)? How about by a repunit?

[This has been cross-posted to MO.] A positive integer $N$ is said to be a perfect number if $$\sigma(N) = 2N,$$ where $\sigma(x)$ is the sum of the divisors of $x$. For example, $6$ is perfect ...
4
votes
1answer
125 views

Is the totient function $\varphi$ invertible?

As title, is the totient function $\varphi: \mathbb{N} \to \mathbb{N}$ invertible?
5
votes
2answers
245 views

Prove that $\sum \limits_{d|n}(n/d)\sigma(d) = \sum \limits_{d|n}d\tau(d)$

How can I prove: $$\sum \limits_{d|n}(n/d)\sigma(d) = \sum \limits_{d|n}d\tau(d)?$$ Few observations : Left side is a sum function and the right side is a number of divisors function. Both the sides ...
3
votes
2answers
118 views

Finding $23! 7! \bmod 29$ using Wilson's Theorem

I'm trying to reduce $23!\,7! \bmod 29$. I used Wilson's Theorem to get $23!(120)\equiv 1 \pmod{29}$. I then solved $120a\equiv 1 \pmod{29}$ and got $a\equiv 22$. I then computed $7! \pmod {29}$. ...
2
votes
1answer
73 views

The perimeter of triangle $ABC$ where $|BC|=293$, $|AB|$ is a square, $|AC|$ is a power of $2$, and $|AC|=2|AB|$

In triangle $ABC$ length of side $BC$ is $293$ (a prime). If length of side $AB$ is a perfect square, length of side $AC$ power of 2 and $AC$ twice length of $AB$, find the perimeter. Kind of ...
5
votes
0answers
174 views

Diophantine: $x^3+5=y^5$

Find all integers $x$ and $y$ such that $x^3+5=y^5$. I found this after solving the equation $3^a+5=2^b$. For this equation, since $(a,b)=(3,5)$ is a solution, it is possible to write it as ...
2
votes
3answers
1k views

Infinite geometric progression involving square terms

The sum of an infinite geometric progression is 15 and the sum the squares of these terms is 45. Find the series. The formula for sum of infinite GP is $\frac{a }{1-r} $ and I got two equations ...
4
votes
2answers
145 views

Why is there a 'missing' $1$ in the Euler–Mascheroni constant?

It is easy to show that: $$ \sum_{k=1}^n \frac{1}{k} > \ln(n+1), $$ but the Euler–Mascheroni constant is defined as: $$ \gamma = \lim_{n \to \infty} \left( \sum_{k=1}^n \frac{1}{k} - \ln(n) ...