The Lord says that Father is His God also in John's Gospel (John 20:17), and this does not annul in any way the fact that He is God, as He is called in the same Gospel (John 1:1-3).
The Lord here speaks with regard of His human nature, for with regard of Him as human, God the Father is His God, how otherwise? Could the Lord's humanity, that is created, be outside of being subjected to God? But who created this humanity? Only the Father or also the Son? Of course also the Son, for we know that nothing is created or, in fact, can be created by Father alone without His Logos, the Latter being the ontologically necessary means for the Father to create anything. Therefore, we can say that with reference of Christ's human nature, Logos is also, alongside with the Father God of Jesus Christ; thus, yes, paradoxically (to avoid horrible Nestorian pitfall that puts two persons in Christ, one divine uncreated Person of Logos and the second created person of Jesus), we can say that Christ is God of His own human nature alongside with the Father, necessarily so, because Both have created this human nature and Creator is God with reference to the created.
Indeed, when He says in John's Gospel "I ascend to the Father" (John 20:17), does He speak from the perspective of His human nature or divine nature? Of course from the perspective of His human nature, for as Father-God's co-eternal Logos-God He is always there with the Father inseparably, on the same level, so how He can ascend to where He already and eternally and inseparably is? ("Even the Son of Man, who is in Heaven" (John 3:13), i.e. in Heaven, that is to say, on the same level, with the Father who is also in Heaven (Matthew 6:9).
And even in this very passage the divinity of Christ is very clearly seen, for He features here as the Principle who puts divine name in humans, who will therefore have this name in them, thus, derivatively, through Christ; and just like the Principle of creation of humans is the Son alongside with the Father, so that the Father cannot ontologically create them without the Son-Logos, similarly the Father can divinize humans - which is the meaning of the expression "His name being put on them" - only through Christ, who is just as ontologically necessary for the Father in this deed, as He (Christ) is ontologically necessary for Him (Father) to create the universe. Now, anything or anyone which is necessary for God to do something, that is to say, anything or anyone without which or whom God is impotent to do something, is God also, just like, to use a patristic simile, the sun-disc is impotent to enlighten without its rays, the latter being also the sun (as we say, usually, "sun has burned my skin" meaning both the disc and the rays of the sun).
And moreover Christ features in this passage as the Principle who makes the pillarhood of the saved men eternal in the Temple ("never shall he go out"), thus Himself possessing the eternal abiding out of His own authority through which He confers the eternal abiding also to humans derivatively. And, furthermore, the "conquerers" will become such abiding pillars, but conquerers of what? Of course of their sins and demonic powers, for nobody snatches or forces his way into the Kingdom without this conquering (Luke 16:16), but men cannot conquer without the Him who is the first Conquerer, the Lord Jesus Christ (John 16:33), for only through Him being and working in us, by co-working with Him, we can defeat the enemy (1 John 4:4) and go to the Father.
Thus, Christ is God and the Father is His God, - no theological problem or contradiction whatsoever!