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

learn more… | top users | synonyms (1)

0
votes
1answer
60 views

Evaluate the remainder efficiently

Suppose I'm having a number containing N 1s in the form of 1111...1 and I want to evaluate the remainder of this number divided by M. Both N and M can be large, is there an efficient way to do this?
5
votes
2answers
244 views

Prove that expression is never an perfect square.

Prove that $(n-2)(n-1)n(n+1)(n+2)$ is never a perfect square for $n \ge 3$. I've the following progress: $\gcd(n^2-1,n^2-4) = \gcd(3,n^2-4)$ which is either $1,3$. When the $\gcd$ is $1$ it's ...
5
votes
1answer
68 views

Show that each integer of the form $a^2+b^2$ has all the factors of this form, where $(a, b)$ are distinct integers and relatively prime

Show that each integer of the form $a^2+b^2$ has all the factors of this form, where $(a, b)$ are distinct integers and relatively prime Progress If $a^2+b^2$ is prime then it is already proved, ...
1
vote
0answers
34 views

Characterizing Coprimes

Here's a question about coprimes that I stumbled upon while doing some research. Providing insight into this question would prove quite helpful to me. Choose a pair of coprimes $x, y \in \mathbb Z$. ...
3
votes
2answers
97 views

Which natural numbers can be represented as a sum of natural numbers raised to different powers?

Waring's problem asks about natural numbers that can be represented as a sum of natural numbers all raised to the same power $k$. I'm wondering which natural numbers can be represented as a sum of ...
7
votes
3answers
644 views

How to find natural solutions of an equation?

When I'm solving problems, I'm often confronted to solving equations, and when I'm solving equations, I'm often confronted to find the natural solutions of these equations. My actual personal ...
1
vote
1answer
29 views

Prove the Relations

Let $\operatorname{ord}(a \mid n)$ denote the order of $a$ modulo $n$. Given $\operatorname{ord}(a \mid n)$ and $\operatorname{ord}(b \mid n)$ find $\operatorname{ord}(ab \mid n)$ and ...
3
votes
2answers
187 views

What's the formula for the fixed point of a power tower of $2$s modulo $n$?

e.g., $n = 3$. Clearly, the powers of $2$ modulo $3$ alternate $2, 1$. The powers of $4$ modulo $3$ are all $1$s. So a power tower of $2$s modulo $3$ must get stuck on $1$. Of course this method is ...
1
vote
4answers
64 views

Integer equation with one parameter

I need to find positive integers $f = f(n)$ and $g = g(n)$ both dependent on $n \in \mathbb N$ so that $$ \frac1g + \frac1f = \frac{3}{3n-2} $$ for all $n$ (Or at least all $n>N$ where $N$ is a ...
0
votes
1answer
47 views

Clarification on The Trichotomy Law

I'm getting this from Spivak's, "Calculus" 4th ed. Pg 9. If $P$ is the collection of all positive numbers, how is $-a$ in the collection $P$? Does it mean for some positive number $b$ there exist ...
1
vote
2answers
44 views

Regarding square-free numbers and their doubles.

Is it true that between any non-prime square-free number and it's double is another non-prime square-free number?
0
votes
2answers
67 views

fundamental theorem of arithmetic problem

Change machine contains n quarters, 2n nickels, 4n dimes, n positive integer. Find all values of n so that these coins total k dollars, k positive integer. My thinking is to reduce coins to prime ...
3
votes
2answers
197 views

Prove a basic result in modular arithmetic

I’ve been taught that if $a \equiv b$ and $c \equiv d \pmod {m}$, then $a +c \equiv b+d \pmod{m}$ and $ac \equiv bd \pmod {m}$. But I would like to know how one can prove it. Can you give me a hint? ...
0
votes
1answer
48 views

Summation and product over $k$ with $k$ prime to $n$ sought

I just come to a standstill with the following two formulas. If $$E_n=\lbrace k\mid 1\le k\le n\ \&\ (k,n)=1\rbrace$$ then I hope for a closed formula $f(n)$ for those $$\sum_{E_n}k$$ ...
2
votes
0answers
31 views

floor function inequality $\frac{3c-3n-3}{2n+3} \geq \lfloor\frac{3c-3n}{2n+3}\rfloor$

I want to prove following statement: $$\forall K\in \mathbb R \exists c\in \mathbb N c\geq K s.t.\forall n\in \left\{1,2,...,c-1\right\}: \frac{3c-3n-3}{2n+3} \geq \lfloor\frac{3c-3n}{2n+3}\rfloor$$ ...
4
votes
2answers
150 views

Solving $x^3+y^3=x^2y^2+1$ in non-negative integers

I wanted to solve $x^3+y^3=x^2y^2+1$ in non-negative integers. First I set $a=x+y$ and $b=xy$ to get $b^2+3ab+1=a^3$. View as a quadratic in $b$, the discriminant = $4a^3+9a^2-4$, which needs to be a ...
0
votes
1answer
61 views

Solve for x,y: $x^2+1=2y^2$

Solve for integers $x,y$ such that $x^2+1=2y^2$? I tried factoring as $(x-y)(x+y)=(y-1)(y+1)$ but couldn't continue from here, I would appreciate any help. Thanks!
2
votes
2answers
296 views

Intersection of a non-empty set of natural numbers (set-theoretic definition) is a natural number?

This question is very similar to Intersection of a non-empty set of natural numbers (set-theoretic definition) gives an element of that set? Consider the following set-theoretic definition of natural ...
0
votes
3answers
125 views

$6n+1$ and $6n-1$ prime format [duplicate]

I recently stumbled upon a fact that all prime numbers past $3$ are of the form either $6n-1$ or $6n+1$. Is it true? at least for numbers less than $10^9$. And does it cover all primes?
1
vote
1answer
186 views

Intersection of a non-empty set of natural numbers (set-theoretic definition) gives an element of that set?

Consider the following set-theoretic definition of natural numbers: $0$ is defined as $\emptyset$ If $n$ is defined, then the successor of $n$ is defined as $n^+ = \{n\} \cup n$ Thus $1 = \{0\}$, ...
0
votes
1answer
101 views

What percent of numbers are primes? [duplicate]

I understand that there are infinitely many primes and (obviously) infinitely many integers, but is there any way to calculate the total percentage of integers that are primes? Thanks
4
votes
2answers
482 views

Is this proof that there are no perfect, odd, integer square numbers legitimate?

Assumptions: Any even number times any other number is always an even number. An odd number times an odd number is always an odd number. An even number plus an even number is even, and an odd number ...
1
vote
2answers
130 views

How to simplify the formula for $n$th Fibonacci number when $n=2$?

When n is equal to 2 how do I simplify when the $n=2$ is put into the equation below (by the way I have to prove this formula by induction that when n= any number it will equal that number) ...
2
votes
2answers
75 views

Diophantine: $px^2+2=y^2$ where $p\in \mathbb{P}$

Solve the Diophantine Equation: $px^2+2=y^2$, where $p$ is a prime number and $x,y$ integers. I tried this for ages but didn't get anywhere, but I don't know any advanced machinery since I am only in ...
1
vote
4answers
87 views

Why does gcd(a,n) have to be 1 for there to exist a $d$ such that $a^d \equiv 1 \pmod{n}$

In the definition for multiplicative order, one of the requirements is that the modulo and the base are coprime. That is, if there exists some order $d$ such that $$a^d \equiv 1 \pmod{n}$$ then ...
1
vote
1answer
101 views

Sum of all possible remainders when $2^n$, where n is a nonnegative integer, is divided by 1000

Let $R$ be the set of all possible remainders when a number of the form $2^n$, $n$ a nonnegative integer, is divided by $1000$. Let $S$ be the sum of all elements in $R$. Find the remainder ...
3
votes
1answer
352 views

Prove that the Möbius function is multiplicative

I'm studying algebra, and I came across some questions on multiplicative functions (that should be number theory though?). One is: prove that mobius function is multiplicative. But I've not been given ...
0
votes
4answers
77 views

Is there a listing of natural numbers with their properties?

I am looking for a category of natural numbers (about <1000 is enough) with its properties. Here's some examples : 2 - It is the first prime number. 1729 - It is the smallest number expressible ...
1
vote
3answers
134 views

Prove that a function $f(n)$ counting the number of odd divisors multiplicative

How can I show that $f(n)$ is multiplicative, where $f(n)$ represents the number of the divisors of n in the form $2k + 1$? I'm studying algebra and I came across some questions on multiplicative ...
1
vote
1answer
75 views

Integer solutions for an equation

I am looking for an expression yielding all the integers $a\geq 0$ such that $$ \frac{ab}{c}-\frac{cd}{2} $$ is integer, given $b$ and $c$ are integers, $d$ is rational, $b\geq 1$, $c\geq 1$ and ...
0
votes
2answers
36 views

Substitution of rational values of cosine function

If $x$ and $y$ are integers $>0$ and $0 < \theta < \pi/2$ is a real number such that $y = x\cos \theta,$ can one conclude that $$\frac{y}{x} = \frac{1}{2}?$$ Under what conditions $\cos ...
1
vote
2answers
57 views

Is gcd(a, b) = gcd(a mod b, b)?

It seems to be the case for every pair of positive integers where $a>b$ but I can't really think of a way to proof this.
2
votes
1answer
98 views

How can “Lucky Numbers” be approached rigorously?

To begin with, "Lucky Numbers" are a sequence of numbers generated by a sieve similar to the Sieve of Eratosthenes for finding primes. It starts with the set of natural numbers. Begin by selecting ...
2
votes
2answers
47 views

Finding a two-digit number.

The sum of the digits of a two-digit number is $9$. When we intrchange the digits,it is found that the resulting new number is greater than the original number by $27$. What is two digit number?
1
vote
3answers
49 views

Finding number given least common multiple with $24$

Is there any easier or algorithmic method to solve this problem? There are two numbers, $n$ and $6$. The least common multiple of $n$ and $6$ is $24$. Find $n$. The way I do this is by ...
1
vote
1answer
72 views

If $n$ is any positive integer whose last digit is $5$, then $5$ divides $n$

Prove that if n is any positive integer whose last digit is a 5, then 5|n Therefore, n is going to be 5, 15, 25, 35 etc ... b∣a states that 'b divides a' and we know that 5∣5, 5∣15, 5∣25, 5∣35 ...
4
votes
5answers
692 views

Proof by induction: $n$th Fibonacci number is at most $ 2^n$

I'm trying to find the proof by induction of the following claim: For all $n\in\mathbb N$, $\operatorname{fibonacci}(n) \le 2^n$ My Proof: Base case: $n = 1$ $\operatorname{fibonacci}(1) \le 2^ 1$ ...
1
vote
1answer
143 views

A sequence of subsets of $\Bbb Z$ not containing nontrivial subgroups

Is there a sequence $(A_n)$ of subsets of $\Bbb Z$ such that always $\{a-b\mid a,b\in A_{n+1}\}$ is a proper subset of $A_n$ and no $A_n$ contains an infinite subgroup of $(\Bbb Z,+)$? (Ed.: this ...
7
votes
5answers
759 views

Is the product of uniformly distributed numbers, uniformly distributed too?

My question is simple, I think. If we took two random natural numbers $a$ and $b$ uniformly distributed in a specific range $[c,d]$, is $ab$ a uniformly distributed too? What if $a$ and $b$ are not ...
2
votes
2answers
43 views

Proof of an equality involving $\phi(n)$

I would like to prove the following equality: $$k^{\phi(l)} + l^{\phi(k)} \equiv1\pmod{lk}$$if $\gcd(l,k)=1$. What methods can I use? Thank you for your help.
2
votes
4answers
93 views

Let $n \in \mathbb {Z}$. If $n^2$ is even, then $n$ is even.

I think that a proof by contrapositive can do, but I don't know how to complete it. Assume that $n$ is odd. Then, $n=2k+1$ for some integer $k$. Therefore, $n^2= (2k+1)^2 = 4k^2+4k+1$. I know that ...
6
votes
3answers
226 views

Towards a formula for the Euler $\phi$ function?

$\Phi_n(1)$ and $\Phi_n(-1)$ for the cyclotomic polynomials are well-known. I am now looking for $$\Phi_n(i)$$ and/or $$\Phi_n(-i)$$ with $i$ the complex unit. The reason is : I suppose it is ...
0
votes
2answers
45 views

How to solve equation in complex numbers?

For $n$ odd ( e.g. with $n\equiv 1\mod 4 )$ I seek a solution $f(n)$ for this simple equation in the complex numbers $$(-1)^{f(n)}2^{\frac{n-1}{2}}=-\frac i2(1+i)^{n+1}$$ $f(n)$ is probably an integer ...
3
votes
1answer
238 views

Fermat: Prove $a^4-b^4=c^2$ impossible

Prove by infinite descent that there do not exist integers $a,b,c$ pairwise coprime such that $a^4-b^4=c^2$.
2
votes
3answers
127 views

Solution of equation $ x^2\equiv 1 \pmod{784}$

How to solve the equation $ x^2\equiv 1 \pmod{784}$ ? Context I know the Chinese Remainder theorem, but have no idea how to begin. Could you give me any clue? The only thing that I would like to is ...
6
votes
3answers
256 views

How to express “b is a power of 10” – Typographical Number Theory in Gödel Escher Bach

The book Gödel, Escher, Bach (GEB) by Douglas R. Hofstadter introduces a formal system called “Typographical Number Theory” (TNT). It's essentially first order predicate logic over the universe of ...
3
votes
1answer
55 views

Why do we assume relatively primes?

How to prove that for all $m,n\in\mathbb N$, $\ 56786730 \mid mn(m^{60}-n^{60})$? Why do we assume that $$(m,61) = 1\wedge (n,61) = 1 $$ ? I mean why it is possible ?
3
votes
2answers
92 views

prove/verify prime division

$a_i$ positive integers for $1\le i\le n$ if $p$ prime and $p\mid a_1a_2\cdots a_n$ then $p\mid a_i$ for some $1\le i\le n$: My thinking is to prove it by contraposition. $p$ does not divide ...
4
votes
2answers
161 views

Solving $x^2 - 11y^2 = 3$ using congruences

I'm looking to find solutions to $x^2 - 11y^2 = 3$ using congruences. The question specifically asks "Can this equation be solved by congruences (mod 3)? If so, what is the solution? (mod 4) ? (mod ...
3
votes
2answers
149 views

Proof: no fractions that can't be written in lowest term with Well Ordering Principle

My question is the exact same question as the one in this post but I commented on it but it's from a year ago so I just wanted to bump it and see if I could get a response: Prove that there's no ...