Questions on more advanced topics of number theory. Consider first if (elementary-number-theory) might be a more appropriate tag before adding this tag.

learn more… | top users | synonyms (1)

1
vote
4answers
55 views

Number of divisors of a product

Let $a$ and $b$ be the number of divisors of two positive integers , is it possible to explicitly express the number of divisors of their product only in terms of $a$ and $b$? If not , how can it be ...
3
votes
3answers
47 views

Lowest multiple with given condition

I've got this interesting problem: Find the lowest multiple of $130013$ that consists of only digit $9$ in base-$10$ numeral system. It came down to finding the lowest $n$ such that: ...
0
votes
3answers
202 views

Use the Chinese remainder theorem to find the general solution of $x \equiv a \pmod {2^3}, \; x \equiv b \pmod {3^2}, \; x \equiv c \pmod {11}$

Help! Midterm exam is coming, but i still unable to solve this simple problem using the Chinese remainder theorem. $$x \equiv a \pmod {2^3}, \quad x \equiv b \pmod {3^2}, \quad x \equiv c \pmod ...
0
votes
3answers
99 views

Integers satisfying condition - highest common factor of $(n,36)$ is $1$

How many integers $n$ in the range of $2 \leq n \leq 1000$ which satisfies the following condition Highest common factor of $(n,36)$ is $1$?
0
votes
2answers
44 views

What are all the values of $ x \equiv a^\frac{p-1}{2} \pmod p$

Suppose p is an odd prime and a $\in$ $\mathbb{Z}$ such that $ a \not\equiv 0 \pmod p$. What are all the values of $ x \equiv a^\frac{p-1}{2} \pmod p$ ? This is what I got so far: $ x^2 \equiv ...
0
votes
2answers
68 views

How find this value $\overline{a_{1}a_{2}a_{3}a_{4}a_{5}}=?$

if the $a,b,c,d,e$ is $a_{1},a_{2},a_{3},a_{4},a_{5}$ a permutation and $a_{i}\in[0,9],a_{i}\in N$,such $$\overline{abcde}=5\overline{a_{1}a_{2}a_{3}a_{4}a_{5}}$$ Find the ...
0
votes
2answers
82 views

Proving that $fib(n) < (5/3)^n$ for $n \ge 1$ by induction

I know this has been shown before here but no post really answered my question. I had this problem given to me as an induction practice problem and I couldn't solve it without help. When I got the ...
0
votes
2answers
115 views

How to solve a congruence of a polynomial $x^3+2x^2+x+2\equiv 0 \mod 45$?

$x^3+2x^2+x+2\equiv 0 \mod 45$ $f(x)=(x^2+1)(x+2)$ by inspection $\fbox{1}$$x=7$ is a possible solution $\mod 9$ ,since $45=5\times 3^2$ $\fbox{2} $ $x= 2 $ is a solution $\mod 5$ but i want to ...
0
votes
2answers
94 views

Using induction to prove that every integer can be written in a particular form

(a) Use induction to prove that every integer $n$ can be written in the form: $$n = \beta_0 3^0 + \beta_1 3^1 + \cdots + \beta_{r-1} 3^{r-1} + \beta_r 3^r$$ where $r$ is a non-negative ...
0
votes
2answers
66 views

Find all rational zeros of the polynomials:

Find all rational zeros of the polynomial $$ f(x)=(4x^6)+(3x^5)-(7x^4)+(3x^2)+(27x)-63 $$ Find all rational zeros of the polynomial $$ g(x)=(15x^3)-(2x^2)+x+14 $$
0
votes
2answers
197 views

find a general expression for the remainder when a prime divides a fibonacci.

I have primes of form $5k\pm1$. Consider the equation: $F_n=f(n)\pmod p$ where $F_n$ is the nth fibonacci number. Now given a c, how can i check whether or not there exists a solution for $f(n)=c ...
0
votes
2answers
33 views

Demonstration congruences

Assuming that $m=p_1^{\alpha_1}...p_r^{\alpha_r}$. Show that $$a\equiv b\pmod m\Longleftrightarrow a\equiv b\pmod {p_i^{\alpha_i}},\;i={1,...,r}$$ I always thought very beautiful statements that ...
0
votes
2answers
36 views

If $a,m,n \in \mathbb{Z}$ with $m>0, n >0$, Prove that [$a^m]=[a^n]$ in $\mathbb{Z_2},$

Hello I need help with this proof If $a,m,n \in \mathbb{Z}$ with $m>0, n >0$, Prove that [$a^m]=[a^n]$ in $\mathbb{Z_2},$
0
votes
2answers
54 views

Factorization of Primes and Greatest Common Divisors

If $a=q_1^{e_1}q_2^{e_2}...q_r^{e_r}$ and $b=s_1^{f_1}s_2^{f_2},...s_u^{f_u}$ are the factorizations of $a$ and $b$ into primes, then there exist primes $t_1<t_2<...<t_v$ and nonnegative ...
0
votes
2answers
106 views

Divisor Function

Divisor Function d(N) is the number of divisors of N less than or equal to N. Ex. d(1)=1,d(2)=2,d(10)=4...so on.... I had a question that says to compute answer to function ...
0
votes
2answers
61 views

When $a$ is even, the difference between $(a/2) \mod N$ and $(a \mod N)/2$?

folks. Could I ask for your help? Let $N$ be a positive integer and $a$ be an even integer, i.e., $a=2x$ for an integer $x$. Then think of $W_N^{\frac{a}{2}}$, where $W_N=e^{j\frac{2\pi}{N}}$. ...
0
votes
2answers
43 views

Number of solutions of equation of the form $a (x^{2}) + b (y^{2}) = n$

I wanted to find the number of solutions to the equation of the form $a (x^2) + b (y^2) = n$. I was trying to implement Sieve of Atkin but I have no idea how to find the number of solutions to such ...
0
votes
2answers
104 views

discrete math counting problem

I am majoring in philosophy and currently im taking a logic course. I am having trouble with this question and I think you all mathematicians could help me out. There are five philosophy majors, four ...
0
votes
2answers
54 views

Binary Vector Communication

Alice holds an $n$ x $n$ binary matrix $A$, and Bob holds an $n$ x $n$ binary matrix $B$. They want to check whether $A = B$, but they do not want to communicate too much. Here is what they do: Alice ...
0
votes
2answers
96 views

Prove using lcm of a number to find there exists n consecutive numbers for which f is constant & finding the greatest number of elements of a set?

Let f : N \ {0,1} --> N be a function defined by f(n) = lcm[1, 2, ..., n]: (a) Prove that for all n, n >= 2, there exist n consecutive numbers for which f is constant (i.e. some numbers a, a + 1, ...
0
votes
2answers
68 views

Showing $\mathrm{ord}_d(a) \mid \mathrm{ord}_m(a)$ if $d \mid m$

Let $1\le d$, $1 \le m$ where $d \mid m$. Suppose that $\gcd(a,m)=1$ (and so $\gcd(a,d)=1$). Prove that $\mathrm{ord}_d(a)$ divides $\mathrm{ord}_m(a)$.
-1
votes
2answers
60 views

Find and PROVE all values of n which one of the following relations hold true:

In addition to finding we must prove our answers. Find all values of n for which one of the following relations holds true: $\phi(n)=n/2$, $\phi(n)=n/3$, and $\phi(n)=n/6$. Then in general, let ...
-2
votes
2answers
98 views

Even or Odd for factorial

Moderator Note: This is a current contest question on codechef.com. Given $N$ and $M$ I need to tell whether $\left\lfloor \large\frac{N!}{M} \right\rfloor$ is even or odd.How to do this ...
-2
votes
2answers
68 views

Finding modulus of two numbers

Let $\frac xy$ be a fraction in reduced form, $y\geq x$, and $m=y \mod x$. How do you find $x$ mod $m$?
-2
votes
2answers
120 views

Show that there are infinitely many $n$ such that $\sigma(n) \le \sigma(n-1)$.

Show that there are infinitely many $n$ such that $\sigma(n) \le \sigma(n-1)$. Looking for a proof to show there are infinitely many $n's$ for this problem. Thanks