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

learn more… | top users | synonyms

2
votes
3answers
89 views

Showing that a composite number has a small prime divisor?

At the moment I'm working on proving some statements and I've run into one that I can't seem to wrap my head around. It goes like this: For $n \in \mathbb{Z}^+$, we define $\sqrt{n}$ as the real ...
3
votes
2answers
123 views

Three digit number $ABC$ with $ABC = A + B^2 + C^3$

Is there a trick for solving this problem about number of digits? $ABC$ is a three-digit natural number, such that $ABC = A + B^2 + C^3$. According to above equation what is $ABC$ ?
1
vote
1answer
44 views

Multiples of 11 in a Fibonacci-like sequence formed by concatenation instead of addition

Let $A_1=0$ and $A_2=1$ and suppose that the number $A_n$ is obtained from the decimal expansions of $A_{n-1}$ and $A_{n-2}$. For example $A_3=A_2A_1=10$; $A_4=A_3A_2=101$; $A_5=A_4A_3=10110$. ...
3
votes
4answers
64 views

Proof of divisibility using modular arithmetic: $5\mid 6^n - 5n + 4$

Prove that: $$6^n - 5n + 4 \space \text{is divisible by 5 for} \space n\ge1$$ Using Modular arithmetic. Please do not refer to other SE questions, there was one already posted but it was using ...
9
votes
1answer
168 views

Find all distinct positive integers $a,b,c,d,e$ with some given conditions.

Find all distinct positive integers $a,b,c,d,e$ such that ...
3
votes
1answer
53 views

Deceptively simple divisibility problem

Suppose we are given integers $a,b$ with the condition that there exists a prime $k$ such that $$2a+b\mid (a+b)^k$$ What can we say about $\gcd(a,b)$? So far, I can see that for all primes $p:p\mid ...
2
votes
2answers
59 views

Clarification regarding Prime theorem

This is one theorem which I came across the book: For every positive integer $n$, there is a sequence of $n$ consecutive positive integers containing no primes. Is this theorem valid ? Because ...
2
votes
2answers
115 views

prime factors of number with a particular form

I try to factorize this huge number $2^{(3^{(5^7)})} +7^{(5^{(3^2)})}$ .but i have no idea,the only thing i know is that it's not divisible by 7 and 11. can you help me find some prime factors of ...
3
votes
2answers
283 views

Magical properties in “2015”?

This question is inspired by one particular answer to a riddle for 2015 Here's the answer copied in full below: $2015+9=2024$ $2024\div 8=253$ $253-7=246$ $246\div 6=41$ ...
1
vote
1answer
45 views

Show that $\lim_{n \rightarrow \infty} \left(\prod_{i=1}^{n} (a_i+1) \right)^{1/n} $ using Birkhoff Ergodic Theorem

Show that for Lebesgue-almost every $x \in [0,1)$, the geometric mean $$\lim_{n \rightarrow \infty} \left(\prod_{i=1}^{n} (a_i+1) \right)^{1/n} $$ exists and has common value. What is this? (no ...
3
votes
3answers
87 views

Pythagorean type diophantine equation.

How to find all solutions to $$ a^2+b^2+c^2+d^2=e^2+2$$ where all variables $a$ to $e$ are positive integers and $e^2 \equiv 1 \mod 8$ I tried using parameterization similar to ...
1
vote
1answer
70 views

How to prove that there exist $m,n,p,q\in [1,n]$ such that $\text{Icm}[a_{m},a_{n},a_{p},a_{q}]\ge n^2$

Question: let $a_{1},a_{2},a_{3},\cdots,a_{n}(n>100)$ be quie different postive integers,and suc for any quite different postive integer $i,j,k,l\in [1,n]$,have ...
0
votes
1answer
41 views

existance of decimal expansion

Can every real number be written in decimal expansion? I mean, can every real number $a$ be expressed as follows: $$\text{For }\, a \in \mathbb {R}^{+},\quad ...
2
votes
2answers
85 views

Proving $310 \mid n^{121}-n$ for all integers $n$

I wrote it as $n^{120}=1\pmod{310}$ and thought I'd divide it in simpler congruences with primes (is this right?) $$n^{120}=n^{4\cdot30}=1\pmod{31}$$ $$n^{120}=n^{30\cdot4}=1\pmod{5}$$ But then I'm ...
0
votes
1answer
46 views

Use totient function to find the number of factors prime to 720

What is totient function? the solution given shows a function phi and directly solves it. Could you guys help me?
1
vote
2answers
69 views

$N=2^7\cdot3^5\cdot5^6\cdot7^8$. How many factors of $N$ are divisible by $50$ and not by $500$?

My attempt: $50=5^2 \cdot 2$ $500=5^3 \cdot 2^2$ Factors divisible by $50=5 \cdot 7 \cdot 6 \cdot 9=1890$ Factors divisible by $500=4 \cdot 6 \cdot 6 \cdot 9=1296$ So, the answer is ...
4
votes
2answers
79 views

Prove: for all $n$ there's a $m$ such that the sum of digits in $mn$ is equal to $n$. [closed]

In the following $n,m$ are natural numbers. I need to prove that for all $n$ there's a $m$ such that the sum of digits in $mn$ is equal to $n$. Any ideas? Thanks.
1
vote
1answer
20 views

$m<n$ is which rank of numbers who has scratched?

I find prime numbers with Sieve of Eratosthenes for numbers from 1 to $n$. How many numbers has scratched before $m$. For $1\leq m\leq n$?
3
votes
3answers
62 views

How many sets of two factors of 360 are coprime to each other?

My attempt: $360=2^3\cdot3^2\cdot5^1$ Number of sets of two factor coprime sets for $2^3$ and $3^2$ only $=12+6=18$ With that if we add the effect of $ 5^1$, number of sets=18+2*18-1=53. Is this ...
10
votes
2answers
126 views

Show $1+x+(x^2/2!)+ \cdots + (x^n/n!)=0$ has no rational solutions for all $n>1$.

Prove that the equation $$1+x+\frac{x^2}{2!}+ \cdots + \frac{x^n}{n!}=0$$ has no rational solutions for all $n>1$. Assume there is a rational solution $\frac{p}{q} \in \mathbb{Q}$ with ...
6
votes
1answer
103 views

What is the value of this continued fraction?

I am curious about the value of the continued fraction $$1+\cfrac{1}{2+\cfrac{1}{3+\cfrac{1}{4+\cfrac{1}{5+\cfrac{1}{6+\dots}}}}}.$$ Can we evaluate it ? Is it a nice value ? Clearly it should ...
0
votes
1answer
42 views

Number of trailing zeros at other bases

Q. 85! ends with exactly 20 trailing zeros. When 85! is converted to base N, N being any natural number, it so happens that it has the same number of zeros at the end. What could be the largest ...
1
vote
2answers
57 views

Proving sum of digits of $111111…^2$ is square of sum of digits of $11111…$

How do you prove that the sum of the digits of the square of a number comprised solely of ones is the square of the sum of the digits of that number? For instance, the sum of digits of $111^2$ is 9, ...
2
votes
3answers
81 views

Simplifying $2^{30} \mod 3$

I simply cannot seem to get my head around this subject of mathematics. It seems so counter-intuitive to me. I have a question in my book: Simplify $2^{30}\mod 3$ This is my attempt: $2^{30}\mod 3 ...
0
votes
0answers
75 views

If the Collatz Conjecture is verified upto an integer N, then what can be predicted for integers between N and 2N

If the Collatz Conjecture is verified for all positive integers from 1 to N, then what can be predicted for integers between N and 2N? All even integers in the interval N to 2N would be verified too ...
2
votes
0answers
93 views

prime by reverse listing primes

I also have a particularly interesting/attractive prime sequence and it's: prime $p$ such that the concatenation of first k odd primes(with each prime being reversed) in reverse order from 3 to $p$ ...
1
vote
1answer
14 views

Maximum variance given x values on an interval [a,b]

Thanks in advance for the help. I'm exploring a possible solution to a problem. In order to explore it, however, I need to find the maximum variance of a set of numbers on a given interval. For ...
3
votes
2answers
188 views

Solving an equation for two primes

This is from contest preparation: Find all pairs of primes $(p, q)$ that satisfy $$p^q - q^p = p q^2 - 19$$. It looks simple, but I spent hours trying to solve it... and no luck so far. ...
0
votes
0answers
42 views

Can the difference of two Harmonic numbers be an integer? [duplicate]

It is well known that the Harmonic numbers $$H_n=\sum_{k=1}^n \frac{1}{k}$$ are never integers for $n>1$. Can the difference of two Harmonic numbers $$H_n-H_m=\sum_{k=m+1}^n \frac{1}{k}$$ be ...
2
votes
2answers
52 views

Proof involving Euler totient function and modular arithmetic

Let $ n = pq$ where $p$ and $q$ are distinct primes, and let $e$ be an integer coprime to $ \varphi (n)$. Explain why there is an integer $d$ such that $ed = 1 $ (mod $ \varphi(n)$). Prove that ...
1
vote
1answer
48 views

Computing the difference between two fractions with positive integral variables

What is the difference $U - L$ between the following two fractions, where all variables are positive integers? $$U = \frac{2{b^2}\left({b^2}{2^k}({2^k} - 1) + 2^{k+1} - 1\right)}{(2^{k+1} - ...
4
votes
2answers
42 views

$a_1,a_2,\ldots,a_{11}$ and $b_1,b_2,\ldots,b_{11}$ are $2$ permutations of $1,2,\ldots,11$. Show that atleast…

Let $a_1,a_2,\ldots,a_{11}$ and $b_1,b_2,\ldots,b_{11}$ be 2 permutations of $1,2,\ldots,11$. Show that atleast 2 of $a_1b_1,a_2b_2,\ldots,a_{11}b_{11}$ will have same remainder $\mod 11$ My ...
2
votes
2answers
54 views

Cracking license plate checksum

Suppose a city has license plates assigned to cars with 7 digits $a_1$ to $a_7$ and a checksum calculated by the following algorithm: ($m_k$ are integers) $$m_1a_1+m_2a_2+\cdots+m_7a_7\mod 28$$ (which ...
2
votes
0answers
98 views

How many zeroes would be there at the end of $11^{(5!)!}-1$?

$$11-1=10 \\ 121-1=120 \\ 1331-1=1330$$ Now it can be seen that the tens digit increases by 1 at each increment of exponent. So, only in case of $11^{10}$ the tens digit is zero and the units digit ...
7
votes
0answers
125 views

$(123)!$ divided by $(25!)^x$. What is the maximum possible integral value of $x$?

The answer given is $5$. But I am getting $4$. Here is what I have done. $$25!= 2^{22}\cdot3^{10}\cdot5^6\cdot7^3\cdot11^2\cdot13\cdot17\cdot19\cdot23$$ ...
2
votes
0answers
30 views

The existence of cycles in a composed iterated function ad infinitum.

I originally posted this on MathOverflow, but it was deemed not 'research-level'. The functions I have been concerned with recently are as follows: $\sigma(n^2)$ (divisor function), $P(n)$ (greatest ...
6
votes
0answers
354 views

2015-related question: why are Lucas-Carmichael numbers named after Lucas?

Summary 2015 is a so called Lucas-Carmichael number. I believe (for reasons that I will explain below) that the 'Carmichael' in the name is a reference to ordinary Carmichael numbers and not to the ...
3
votes
1answer
52 views

Efficiently doing prime factorisation by hand

I have a yes/no question first (if 2 questions are allowed in 1 post). When doing prime factorisation for using the Euler totient function can you use a particular prime more than once. (i.e. $p_{1} ...
2
votes
0answers
19 views

Is this sum equal to this convolution?

Consider the matrix $T$ defined by: $$T=a(GCD(n,k))$$ where $GCD(n,k)$ is the Greatest Common Divisor of row index $n$ and column index $k$, and $$a(n) = \lim\limits_{s \rightarrow 1} ...
0
votes
1answer
30 views

Show that $c \notin S $ but that $ n \in S, \forall n \in \mathbb{Z}, n >c$ where $S$ is the following set

Let $a$ and $b$ be positive integers. Set $c=ab−a−b$ and define $S = \left \{ n \in \mathbb{Z}\mid n = ax+by, x \geq 0, y \geq 0 \right \}$ Show that $ c \notin S$ but that $n \in S$ for all ...
9
votes
4answers
2k views

Proving that a number is an integer.

Prove that the following number is an integer: $$\left( ...
1
vote
3answers
63 views

How find $\overbrace{999\dots 9}^{2^{n+2}}\over 99$?

Find $\overbrace{999\dots 9}^{2^{n+2}}\over 99$. Would you help me to find out exact answer?
0
votes
1answer
59 views

L.C.M of consecutive natural numbers

L.C.M of 3 consecutive natural numbers $(a, b, c) = N$. Which of the following is equal to $(a, b) \cdot (b, c) \cdot (c, a)$? (Parentheses denote LCM.) $2N$ $N^2$ $N^3$ not unique cannot be ...
6
votes
1answer
219 views

Prime Number Sieve using LCM Function

How to prove following conjecture ? Definition : Let $b_n=b_{n-2}+\operatorname{lcm}(n-1 , b_{n-2})$ with $b_1=2$ , $b_2=2$ and $n>2$ . Let $a_n=b_{n+2}/b_n-1$ Conjecture : Every term of ...
3
votes
0answers
37 views

Formula for numbers whose iterated distance from next square has fixed point $2$

Consider a function $R: \mathbb N \to \mathbb N,$ $R(n)$ is the distance to the next square greater or equal to $n$. For example, $R(5)=4$ and $R(16)=0.$ Function $R$ has two fixed points, $0$ and ...
0
votes
1answer
19 views

If $\gcd(h,k)=1$ and the order of $a$ modulo $n$ is $h$ and the order of $b$ modulo $n$ is $k$ then show that $ab$ has order $hk$

If $\gcd(h,k)=1$ and the order of $a$ modulo $n$ is $h$ and the order of $b$ modulo $n$ is $k$ then show that $ab$ has order $hk$ So far I figured out $(ab)^{hk} \equiv 1 \pmod{n}$ But this ...
1
vote
1answer
22 views

Determine which quadratic congruences have solutions

I need to determine which congruences of the form $ax^2+bx+c\equiv0\pmod{2}$ have solutions. What I know is that $a,b,c$ are all odd. I admit I have no clue how to begin on this one. This is at the ...
1
vote
1answer
52 views

Prove that $ (p-1)! +1 \equiv 0 \mod p$ [duplicate]

Let p is a prime number. Prove that: $$ (p-1)! +1 \equiv 0 \: \pmod p$$ Could you give me some advice?
7
votes
1answer
69 views

Is Euler product formula equivalent to fundamental theorem of arithmetic (unique factorization theorem)?

Is Euler product formula equivalent to fundamental theorem of arithmetic (unique factorization theorem) ? $$\sum_{n=1}^\infty\frac{1}{n^s} = \prod_{p \text{ prime}} \frac{1}{1-p^{-s}}$$ We know ...
3
votes
2answers
85 views

If $a$ is irrational, does there exist a natural number $n$ such that $na$ is rational?

For some irrational $a$, does there exist an $na$ which is contained within the rational numbers for some natural $n$?